LintCode 乱序字符串

今天做了一道中等难度的字符串题目，这道题目花了我两个小时，不过也做了不少的思考，写篇日志记录一下我的思考过程。

首先是题目内容：
<h4>题目</h4>
给出一个字符串数组S，找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串，那么他存在一个字母集合相同，但顺序不同的字符串也在S中。

<h4>样例</h4>
对于字符串数组 ["lint","intl","inlt","code"]
返回 ["lint","inlt","intl"]
<h4>注意</h4>
所有的字符串都只包含小写字母

我一开始的想法很简单，先写一个算法判断两个字符串是否为乱序字符串，再遍历整个数组S，找出所有的乱序字符串。判断乱序字符串的方法就是把一个字符串放入HashMap当中，使用HashMap<Character, int>记录字符串，如果有重复的字符就把map的value值++，再遍历第二个字符串和第一个生成出来的map，遇到相同的就把HashMap对应char的value减1，减为0就remove掉这个key。

具体是这样的

    public boolean compareStrings(String A, String B) {
        CompareString cs = new CompareString();
        if(B.length() > A.length())
            return false;
        Map<Character,Integer> aMap = cs.StringToMap(A);
        //Map<Character,Integer> bMap = cs.StringToMap(B);
        for(int i = 0; i < B.length(); i++){
            char b = B.charAt(i);
            if (aMap.containsKey(b)){
                if(aMap.get(b) > 1){
                    int times = aMap.get(b)-1;
                    aMap.put(b, times);
                }else
                    aMap.remove(b);
            }else
                return false;
        }
        return true;
    }

    public Map<Character,Integer> StringToMap(String S){
        Map<Character,Integer> sMap = new HashMap<Character,Integer>();
        for(int i = 0; i < S.length();i++){
            char a = S.charAt(i);
            if(sMap.containsKey(a)){
                int times = sMap.get(a)+1;
                sMap.put(a, times);
            }else
                sMap.put(a, 1);
        }
        return sMap;
    }

不过这样的想法虽然可行，但是算法复杂度却有O(n2)那么高！因为要把整个数组S里面的String两两比较一遍，我觉得这太蠢了，一定有更加简单易行的方法。

于是，必须转换思路。

我想到，如果ASCII码来判断两个字符串是否为乱序字符串呢？就好像MD5算法一样，我最后只需要给每一个乱序字符串算出一个特定的数字，用这个数字作为key，把所有等于这个key的字符串放入一个list中，把这个list作为value，用这样的<key, value>组成HashMap，这样我只需要便利一遍字符串数组S，再遍历一遍生成的HashMap，把Map中value的list长度大于1的都放到return list中作为该程序的返回值，问题不就引刃而解了吗！这样算法复杂度只有O(n)，等于用空间换时间了，可行！

于是写出了这样的算法

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class disOrderString {
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    public List<String> anagrams(String[] strs) {
        List<String> disOrderList = new ArrayList<String>();
        Map<Long,List<String>> anagram = new HashMap<Long,List<String>>();
        disOrderString ds = new disOrderString();
        for(int i = 0; i< strs.length;i++){
            String str = strs[i];
            long strAscii = ds.stringToAscii(str);
            System.out.println(strAscii + ":" + str);
            if(anagram.containsKey(strAscii)){
                anagram.get(strAscii).add(str);
            }else{
                List<String> strString  = new ArrayList<String>();
                strString.add(str);
                anagram.put(strAscii, strString);
            }
        }
        Iterator iter = anagram.entrySet().iterator();
        while(iter.hasNext()){
            Map.Entry entry = (Map.Entry) iter.next();
            List<String> list = (List<String>) entry.getValue();
            if(list.size() > 1)
                disOrderList.addAll(list);
        }
        return disOrderList;
    }
   
    //it's unique
    public long stringToAscii(String target){
        long asciiSum = 0;
        int length = target.length();
        for(int i = 0;i<target.length();i++){
            asciiSum += Math.pow(target.charAt(i) - 'a' + 1,7); 
        }
        if(length == 0)
            return 0;
        return (long) (asciiSum*asciiSum/length);
    }
    
    public static void main(String args[]){
        disOrderString ds = new disOrderString();
        String[] strs = {"coroners","crooners","deed","ed","gums","mugs","per","potties","rep","sanity","satiny","smug","tiptoes"};
        List ret = ds.anagrams(strs);
        for(int i = 0; i < ret.size();i++){
            System.out.println(ret.get(i));
        }
    }
}

其中，stringToAscii(String target) 里的加权算法我调整了很多次，最后决定使用7次方，因为7是一个出现频率相对低的质数，而最后返回加权后的ascii码的平方与长度的比值，将字符串长度也考虑到其中，减少误差。最终通过了lintCode 的测试，不过我觉得这个算法依然有改进的空间，当数组足够复杂的情况下，可能依然有误算的情况出现。

7次方的计算是一个非常耗费时间的计算，而楼下评论中有人给出了更简化的算法，思路非常简单，但我当时一门心思钻进了计算hash数值的死胡同里……

链接在此： Find Anagrams

他的思路也是认为每一组乱序字符串都有唯一的相同的“ Hash 值 ”，但是这个值不局限于数值，而是数字和字母的结合，比如 "and" 和 "dan"，他们的“ Hash 值 ”就是“a1d1n1"，"array" 和 "yarar" 就是 a2r2y1，这样就确保了唯一性，算法效率也很高。
代码如下

public ArrayList<String> anagrams(String[] strs) {  
  HashMap<String, ArrayList<String>> hash = new HashMap<String, ArrayList<String>>();  
  for (String str : strs) {  
    // create unique label for each string  
    String key = generalLabel(str);  
    // map the label to a list of anagrams  
    ArrayList<String> res = hash.get(key);  
    if (res==null) {  
      res = new ArrayList<String>();  
      hash.put(key, res);  
    }  
    res.add(str);  
  }  
  ArrayList<String> resSet = new ArrayList<String>();  
  for (ArrayList<String> anagram : hash.values()) {  
    // ignore strings without anagrams  
    if (anagram.size()>1) resSet.addAll(anagram);  
  }  
  return resSet;  
}  

/*  
 * create a unique label for a string  
 * "cat", "atc" => a1c1t1  
 */  
public String generalLabel(String str) {  
  int[] hash = new int[26];  
  for (int i=0; i<str.length(); ++i) {  
    int index = (int)(str.charAt(i) - 'a');  
    hash[index]++;  
  }  
  StringBuilder ss = new StringBuilder();  
  for (int i=0; i<26; ++i) {  
    if (hash[i]==0) continue;  
    char c = (char)('a' + i);  
    ss.append(c);  
    ss.append(hash[i]);  
  }  
  return ss.toString();  
}