Non-Leetcode Questions: Common String in Lists
Given a List of List of String, find the common String in all Lists, output them in sorted order. (could contain duplicates)
Naive Way:Need to consider case [[a,a,a],[a,a],[a,a,b]] outputs [a,a]. Use a HashMap as pattern, go through the lists, for each list, match it with the pattern, update the pattern, what left in the pattern is common string.
Given a List of List of String, find the common String in all Lists, output them in sorted order. (could contain duplicates)
Naive Way:Need to consider case [[a,a,a],[a,a],[a,a,b]] outputs [a,a]. Use a HashMap as pattern, go through the lists, for each list, match it with the pattern, update the pattern, what left in the pattern is common string.
public List<String> commonString(List<List<String>> lists){
List<String> rslt = new ArrayList<String>();
// edge case
if(lists.size()==0) return rslt;
// initialize pattern
Map<String, Integer> pattern = new HashMap<String, Integer>();
List<String> temp = lists.get(0);
setMap(pattern, temp);
// match pattern with other lists
for(int i = 1;i < lists.size();i++){
Map<String, Integer> map = new HashMap<String, Integer>();
setMap(map, lists.get(i));
Iterator it = pattern.entrySet().iterator();
List<String> toBeRemove = new ArrayList<String>();
while(it.hasNext()){
Map.Entry pair = (Map.Entry)it.next();
if(map.containsKey(pair.getKey()))
pattern.put((String)pair.getKey(), Math.min(map.get(pair.getKey()),(int)pair.getValue()));
else
toBeRemove.add((String)pair.getKey());
}
for(int j = 0;j < toBeRemove.size();j++)
pattern.remove(toBeRemove.get(j));
}
// collect results
Iterator it = pattern.entrySet().iterator();
while(it.hasNext()){
Map.Entry pair = (Map.Entry)it.next();
for(int i = 0;i < (int)pair.getValue();i++)
rslt.add((String)pair.getKey());
}
// sort the result
Collections.sort(rslt);
return rslt;
}
private void setMap(Map<String, Integer> map, List<String> list){
for(int i = 0;i < list.size();i++){
if(!map.containsKey(list.get(i)))
map.put(list.get(i), 1);
else
map.put(list.get(i), map.get(list.get(i))+1);
}
} 