educative.io

O(n*k) Solution

Courses
, ,
#1

For this problem I think the below O(n*k) solution is better in terms of time.

1, for comparing anagrams, count each word by different characters, use HashMap<Character, Integer> or an int[128](assuming all characters are ASCII chars). hence the count of each anagram word will be the same. we could use some type of hash to tell whether an int[128] already exists.
So, for each word (length k), we traverse one time to count the characters O(k). we don’t have to sort O(klogk)

2, the rest part could be the same as solution.

#2

Yes I also solved this using O(n*K)

public static String groupAnagrams(String arr[]) {
  //write your code here
  String anagrams = "";
  Map<Integer, List<String>> map = new HashMap<>();
  for(String a: arr) {
      int key = getKey(a);
      if(map.containsKey(key)) {
      map.get(key).add(a);
  } else {
      map.put(key, new ArrayList<>(Arrays.asList(a)));
  }}
  for(Integer key: map.keySet()) {
      anagrams += map.get(key);
  }
  return anagrams;

}

private static int getKey(String s) {
 int sum = 0, prod = 1;
 for(char c: s.toCharArray()) {
     int asc = c - 'a';
     sum += 256 | asc;
     prod *= 256 | asc;
 }
 return sum+prod;

}