[leetcode]Anagrams

新博文地址：[leetcode]Anagrams

Anagrams

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

Note: All inputs will be in lower-case.

 这道题我没看懂啥意思，看了解释之后才知道是从给定的数组中挑出互为anagram的单词，这道题曾经在编程珠玑上看到过，因此没多做考虑就直接开始编码了

具体算法思想是：

对每个单词做出标记，例如对于anagram标记为a3g1m1n1r1，表示这个单词有3个a，1个g等等。

第一遍遍历数组就将所有的单词做出来标记，接下来只需要对比标记即可。

为了优化时间复杂度，在第一遍遍历时，顺便把所有具有相同标记的单词全都丢在了同一个list中。

因此时间复杂度为O(n)

具体代码如下：

public List<String> anagrams(String[] strs) {
		List<String> result = new ArrayList<String>(); 
		Map<String,List<String>> map = new HashMap<String,List<String>>();
		if(strs == null || strs.length == 1){
			return result;
		}
		for(String s : strs){
			String seq = getSequence(s);
			if(map.containsKey(seq)){
				map.get(seq).add(s);
			}else{
				List<String> list = new ArrayList<String>();
				list.add(s);
				map.put(seq, list);
			}
		}
		for(Map.Entry<String, List<String>> entry : map.entrySet()){
			if(entry.getValue().size() > 1){
				for(String s : entry.getValue()){
					result.add(s);
				}
			}
		}
		return result;
    }	
	private String getSequence(String s){
		if("".equals(s)){
			return "";
		}
		int[] hash = new int[256];
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < s.length(); i++){
			hash[s.charAt(i)]++;
		}
		for(int i = 97; i < 123; i++){
			if(hash[i] != 0){
				sb.append((char)i).append(hash[i]);
			}
		}
		return sb.toString();
	}

 第一遍做的时候少考虑了空字符串，实在不应该