今天做了一道中等难度的字符串题目，这道题目花了我两个小时，不过也做了不少的思考，写篇日志记录一下我的思考过程。
首先是题目内容：
<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数值的死胡同里……
他的思路也是认为每一组乱序字符串都有唯一的相同的“ 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();
}
