Find Anagram

出处

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

样例

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

注意

所有的字符串都只包含小写字母

Solution

在题 Two Strings Are Anagrams 中曾介绍过使用排序和 hashmap 两种方法判断变位词。这里我们将这两种方法同时引入!只不过此时的 hashmap 的 key 为字符串,value 为该字符串在 vector 中出现的次数。两次遍历字符串数组,第一次遍历求得排序后的字符串数量,第二次遍历将排序后相同的字符串取出放入最终结果中。

Complexity

时间复杂度 O(n),空间复杂度 O(n)

Code

public class Solution {
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    public List<String> anagrams(String[] strs) {
        List<String> ret = new ArrayList<String>();

        if (strs == null) {
            return ret;
        }

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

        int len = strs.length;
        for (int i = 0; i < len; i++) {
            String s = strs[i];

            // Sort the string.
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String strSort = new String(chars);

            // Create a ArrayList for the sorted string.
            if (!map.containsKey(strSort)) {
                map.put(strSort, new ArrayList<String>());
            }

            // Add a new string to the list of the hashmap.
            map.get(strSort).add(s);
        }

        // go through the map and add all the strings into the result.
        for (Map.Entry<String, List<String>> entry: map.entrySet()) {
            List<String> list = entry.getValue();

            // skip the entries which only have one string.
            if (list.size() == 1) {
                continue;
            }

            // add the strings into the list.
            ret.addAll(list);
        }

        return ret;
    }
}