Group Anagrams

    Given an array of strings, group anagrams together.

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

    Note: All inputs will be in lower-case.

    Python

    1. class Solution:
    2.     # @param strs: A list of strings
    3.     # @return: A list of strings
    4.     # @return: A list of strings
    5.     def anagrams(self, strs):
    7.         if len(strs) < 2 :
    8.             return strs
    9.         result=[]
    10.         visited=[False]*len(strs)
    11.         for index1,s1 in enumerate(strs):
    12.             hasAnagrams = False
    13.             for index2,s2 in enumerate(strs):
    14.                 if index2 > index1 and not visited[index2] and self.isAnagrams(s1,s2):
    15.                     result.append(s2)
    16.                     hasAnagrams = True
    17.             if not visited[index1] and hasAnagrams:
    18.                 result.append(s1)
    19.         return result
    21.     def isAnagrams(self, str1, str2):
    22.         if  sorted (str1) == sorted(str2):
    24.         return False

    C++

    1. strs 长度小于等于1时直接返回。
    2. 使用与 strs 等长的布尔数组表示其中的字符串是否被添加到最终的返回结果中。
    3. 双重循环遍历字符串数组，注意去重即可。
    4. 私有方法isAnagrams用于判断两个字符串是否互为变位词。

    复杂度分析

    私有方法isAnagrams最坏的时间复杂度为 O(2L), 其中 L 为字符串长度。双重for循环时间复杂度近似为 \frac {1}{2} O(n^2), n 为给定字符串数组数目。总的时间复杂度近似为 O(n^2 L). 使用了Vector String “visited”，空间复杂度可认为是 O(n).

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

    leetcode 上此题的 signature 已经更新，需要将 anagrams 按组输出，稍微麻烦一点点。

    Python lintcode

    1. class Solution:
    2.     # @param strs: A list of strings
    3.     # @return: A list of strings
    4.     # @return: A list of strings
    5.     def anagrams(self, strs):
    6.         strDict={}
    7.         result=[]
    8.         for string in strs:
    9.             if  "".join(sorted(string)) not in strDict.keys():
    10.                 strDict["".join(sorted(string))] = 1
    11.             else: 
    12.                 strDict["".join(sorted(string))] += 1
    13.         for string in strs:
    14.             if strDict["".join(sorted(string))] >1:
    15.                 result.append(string)
    16.         return result

    Java - leetcode

    1. public class Solution {
    2.     public List<List<String>> groupAnagrams(String[] strs) {
    3.         if (strs == null) return result;
    5.         // one key to multiple value multiMap
    7.         for (String str : strs) {
    8.             char[] strChar = str.toCharArray();
    9.             Arrays.sort(strChar);
    10.             String strSorted = String.valueOf(strChar);
    11.             if (multiMap.containsKey(strSorted)) {
    12.                 ArrayList<String> aList = multiMap.get(strSorted);
    13.                 aList.add(str);
    14.                 multiMap.put(strSorted, aList);
    15.             } else {
    16.                 ArrayList<String> aList = new ArrayList<String>();
    17.                 aList.add(str);
    18.                 multiMap.put(strSorted, aList);
    19.             }
    20.         }
    22.         // add List group to result
    23.         Set<String> keySet = multiMap.keySet();
    24.         for (String key : keySet) {
    25.             ArrayList<String> aList = multiMap.get(key);
    26.             Collections.sort(aList);
    27.             result.add(aList);
    28.         }
    30.         return result;
    31.     }
    32. }

    源码分析

    第一次遍历字符串数组获得排序后的字符串计数器信息，第二次遍历字符串数组将哈希表中计数器值大于1的字符串取出。

    leetcode 中题目 signature 已经有所变化，这里使用一对多的 HashMap 较为合适，使用 ArrayList 作为 value. Java 中对 String 排序可先将其转换为 char[], 排序后再转换为新的 String.

    遍历一次字符串数组，复杂度为 O(n), 对单个字符串排序复杂度近似为 O(L \log L). 两次遍历字符串数组，故总的时间复杂度近似为 O(nL \log L). 使用了哈希表，空间复杂度为 O(K), 其中 K 为排序后不同的字符串个数。