Anagram总结

有关异构词的题目，考察我们对字符串的处理能力，这里列举leetcode两道关于异构词的题目。
1，Valid Anagram
Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

题目的意思是给定两个字符串，判断它们是否是异构词。
首先我们想到的方法是将字符串转换成字符数组，然后排序之后比较，如果两个新的字符串相同就返回true; 否则返回false；代码如下：

public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        Arrays.sort(s1);
        Arrays.sort(t1);
        s = new String(s1);
        t = new String(t1);
        if(s.equals(t)) return true;
        return false;
    }
}

我们也可以采用一种类似于计数排序的方法来处理这个问题，先将一个字符串中的每个字符按照它们对应的不同的值来存入数组中，然后用第二个字符串中每个字符对应的值减去依次相减，如果数组中有的值不为零就返回false，如果全为0就返回true。代码如下：

public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        int[] count = new int [128];
        for (int i = 0; i < s.length(); i++) 
            count[s.charAt(i) - '0'] ++;
        for (int j = 0; j < t.length(); j++) 
            count[t.charAt(j) - '0'] --;
            
        for(int i = 0; i < count.length; i++) {
            if(count[i] != 0)
                return false;
        }
        return true;
    }
}

2，Group Anagrams
Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:
For the return value, each inner list's elements must follow the lexicographic order.
All inputs will be in lower-case.

题目的意思是给定一个字符串数组，将异构词分组，然后输出。我们借助哈希表，方法类似于第一题中的第一个方法，先排序，然后存放在哈希表中的key中，代码如下：

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hm = new HashMap<String, List<String>>();
        for(int i = 0; i < strs.length; i++) {
            char[] temp = strs[i].toCharArray();
            Arrays.sort(temp);
            String s = new String(temp);
            if(!hm.containsKey(s)) {
                hm.put(s, new ArrayList<String>());
            } 
            hm.get(s).add(strs[i]);
        }
        for(List<String> vals : hm.values()) {
            Collections.sort(vals);
        }
        return new ArrayList<List<String>>(hm.values());
    }
}