Wednesday, October 17, 2012

[LeetCode] Anagrams

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

解题思路:
        寻找回文构词,就是需要建立一个hash函数,使得为anagrams的词都映射到相同的hash key。
      1. 最直接的方法,就是对每个str进行排序,然后比较它们是否相等
      2. 这里我用的是countandsay的方法,就是统计出每个字母出现的次数,然后用字母的次数和字母组合成一个key。
     3. 这个题可以转化为,如何找出2个str为anagrams. 我们可以为每个字母分配一个不同的prime,最后把所有的prime相乘。如果最后的数相等,则为anangrams.

Notice : 这里hash函数的value存的为第一次出现此key的str在数组里的index. 如果出现了此词的anangrams,则将此index. 改为-1。

Java Code:

   
  public List anagrams(String[] strs) {
       List res = new ArrayList ();
       HashMap tmp = new HashMap();

       for(int i = 0; i < strs.length; i++){     
           String key = getKey(strs[i]);
           
           if(tmp.containsKey(key)){
                if(tmp.get(key) != -1){
                   res.add(strs[tmp.get(key)]);
                   tmp.put(key, -1);
               }
               res.add(strs[i]);
              
           }else{
               tmp.put(key, i);
           }
       }
       
       return res;
    }
    
    public String getKey(String str){
        int[] count = new int[26];
        String res = "";
        
        for(int i = 0; i < str.length(); i++){
            count[str.charAt(i) - 'a']++;
        }
        
        for(int i = 0; i < 26; i++){
            if(count[i] > 0){
                res += count[i] + String.valueOf(Character.toChars(i+'a')) ;
            }
        }
        
        return res;
    }

No comments:

Post a Comment