Friday, December 26, 2014

Find Common Characters

Write a program that gives count of common characters presented in an array of strings..(or array of character arrays) 

For eg.. for the following input strings.. 

aghkafgklt 
dfghako 
qwemnaarkf 

The output should be 3. because the characters a, f and k are present in all 3 strings. 

Note: The input strings contains only lower case alphabets

Another Linkedin question. There are various of solutions on Careercup. Overall, the idea is the same: count the existence of each character in each string, if the count equals the length of the input string array, then the character exists in all strings.

I really like one solution using bitset, but there is one comment saying "it doesn't work if there are more than 32 input strings". I tested it, the commenter was correct. And considering all the corner cases I need to take care of, I am using my favorite method: A hash map (I am so in to hash map may be only because my friend said he failed a data scientist because she didn't know how to use a hash map...)!

My solution is based on the same idea as all other solutions. The map size is the number of unique characters in the first string in the array. Because we have to go through the array and check every string, the time complexity is O(mn), where m is the average string length in the array and n is the array length. I don't think we can beat this complexity, can we?
BTW, my solutions works when the array length is 36...



public class CommonCharacters {
 public int getNumOfCommonChars(String[] inputs) {
  if (inputs == null || inputs.length < 2)
   return 0;
  HashMap hm = new HashMap();
  
  for (int i = 0; i < inputs[0].length(); i++) {
   if (hm.containsKey(inputs[0].charAt(i)))
    continue;
   else
    hm.put(inputs[0].charAt(i), 1);
  }
  for (int i = 1; i < inputs.length; i++) {
   String tmp = inputs[i];
   for (int j = 0; j < tmp.length(); j++) {
    if (!hm.containsKey(tmp.charAt(j)))
     continue;
    if (hm.get(tmp.charAt(j)) == i + 1) 
     continue;
    hm.put(tmp.charAt(j), hm.get(tmp.charAt(j)) + 1);
   }
  }
  int count = 0;
  for (Integer ele : hm.values()) {
   if (ele == inputs.length){
    count++;
   } 
  }
  return count;
 }
}

No comments:

Post a Comment