49. Anagrams Leetcode Java

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Solution:

Hashtable

We sort each word in the array, and put them in the hashtable with their index, if it is already in the hashmap, we put the unsorted word into the result list.

Tips: use a boolean array to track if the first one is in the result list, when we found the anagram, we have to put both of them into result list. Using a boolean array can avoid duplication in the result list.

Time Complexity O(n* mlogm) where n is the array length, m is the word length, sorting takes mlogm. Space O(m*n)

 public List<String> anagrams(String[] strs) {  
    List<String> res=new ArrayList<String>();  
    if(strs==null || strs.length==0) return res;  
    HashMap<String,Integer> map=new HashMap<String,Integer>();  
    boolean[] added=new boolean[strs.length];  
    for(int i=0;i<strs.length;i++){  
      char[] temp=strs[i].toCharArray();  
      Arrays.sort(temp);  
      String sorted=new String(temp);  
      if(map.containsKey(sorted)){  
        if(!added[map.get(sorted)]) {  
          res.add(strs[map.get(sorted)]);  
          added[map.get(sorted)]=true;  
        }  
        res.add(strs[i]);  
      }  
      else map.put(sorted,i);  
    }  
    return res;  
   }