Labels

Tuesday, March 3, 2015

Anagrams

Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.

Naive Way: My first thought was use int[26] array to store each word's information, and then use a Map to record that information, once an anagram was found, the int[26] array info will be the same with one of the map. And later I found out that two int[] with same value aren't equal in Java from this post http://stackoverflow.com/questions/2627889/java-hashmap-with-int-array. So I use an ArrayList<Integer> instead.

This algorithm takes O(n) run time and O(n) space. And one corner case I met is when strs[] = {"",""}, the result is ["",""] instead of [""]. It means the second time a particular character appearance list was met, the string must be added into the result.

 public class Solution {  
   public List<String> anagrams(String[] strs) {  
     List<String> rslt = new ArrayList<String>();  
     Set<String> set = new HashSet<String>();  
     Map<List<Integer>, String> map = new HashMap<List<Integer>, String>();  
     for(int i = 0;i < strs.length;i++){  
       // record char appearance into a List<Integer>  
       int[] appear = new int[26];  
       List<Integer> list = new ArrayList<Integer>();  
       for(int j = 0;j < strs[i].length();j++)  
         appear[(int)(strs[i].charAt(j)-'a')]++;  
       for(int j = 0;j < appear.length;j++)  
         list.add(appear[j]);  
       // map list to string  
       if(!map.containsKey(list)){  
         map.put(list, strs[i]);   
       }else{  
         if(!set.contains(map.get(list)))  
           rslt.add(map.get(list));  
         rslt.add(strs[i]);  
         set.add(map.get(list));  
         set.add(strs[i]);  
       }  
     }  
     return rslt;  
   }  
 }  

No comments:

Post a Comment