[LeetCode]--49. 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: All inputs will be in lower-case.

anagrams：由颠倒字母顺序而构成的字

用一个map来存放，map的key存放字符串按字母表字符排序后的顺序，value存放原本的字符串。

public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for (String str : strs) {
            String sortedStr = sortStr(str);
            if (map.containsKey(sortedStr)) {
                map.get(sortedStr).add(str);
            } else {
                map.put(sortedStr, new ArrayList<String>());
                map.get(sortedStr).add(str);
            }
        }
        List<List<String>> res = new ArrayList<List<String>>(map.values());
        for (List<String> list : res) {
            Collections.sort(list);
        }
        return res;
    }

    private String sortStr(String str) {
        char[] charArr = str.toCharArray();
        Arrays.sort(charArr);
        return new String(charArr);
    }

我用的是这个判断是否相同的组成。这种思路也可以供大家参考。

public boolean isTheSameComponent(String a, String b) {
        if ((a == null || a.length() == 0) && (b == null || b.length() == 0))
            return true;
        if (a.length() != b.length())
            return false;
        List<Character> list = new ArrayList<Character>();
        for (int i = 0; i < a.length(); i++)
            list.add(a.charAt(i));
        for (int i = 0; i < b.length(); i++)
            if (list.contains(b.charAt(i))) {
                list.remove((Character) b.charAt(i));
            }
        return list.size() == 0;
    }