LintCode - 乱序字符串（普通）

版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：中等

要求：

给出一个字符串数组S，找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串，那么他存在一个字母集合相同，但顺序不同的字符串也在S中。

注意事项
所有的字符串都只包含小写字母

样例

对于字符串数组 ["lint","intl","inlt","code"]
返回 ["lint","inlt","intl"]

思路：

public class Solution {
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    public List<String> anagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return null;
        }

        List<String> reValue = new ArrayList<String>();
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();

        for (String s : strs) {
            String key = getKey(s);
            if (map.containsKey(key)) {
                map.get(key).add(s);
            } else {
                ArrayList<String> list = new ArrayList<String>();
                list.add(s);
                map.put(key, list);
            }
        }

        for (ArrayList<String> list : map.values()) {
            if (list.size() > 1) {
                reValue.addAll(list);
            }
        }
        return reValue;
    }
    

    /**
     * 生成key（比如 "and" 和 "dan"，他们的“ Hash 值 ”就是“a1d1n1"，"array" 和 "yarar" 就是 a2r2y1）
     *
     * @param s
     * @return
     */
    private String getKey(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int[] count = new int['z' - 'a' + 1];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            count[c - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < count.length; i++) {
            int value = count[i];
            if (value > 0) {
                sb.append(i + 'a').append(value);
            }
        }
        return sb.toString();
    }
}