Group Anagrams

Tags: Hash Table, String, Medium

Question

Problem Statement

Given an array of strings, group anagrams together.

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

  1. [
  2.   ["ate", "eat","tea"],
  3.   ["nat","tan"],
  4.   ["bat"]
  5. ]

Note: All inputs will be in lower-case.

题解1 - 双重for循环(TLE)

题 Two Strings Are Anagrams 的升级版，容易想到的方法为使用双重for循环两两判断字符串数组是否互为变位字符串。但显然此法的时间复杂度较高。还需要 O(n) 的数组来记录字符串是否被加入到最终结果中。

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.                     visited[index2]=True
  17.                     hasAnagrams = True
  18.             if not visited[index1] and hasAnagrams:
  19.                 result.append(s1)
  20.         return result
  22.     def isAnagrams(self, str1, str2):
  23.         if  sorted (str1) == sorted(str2):
  24.                 return True
  25.         return False

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param strs: A list of strings
  5.      * @return: A list of strings
  6.      */
  7.     vector<string> anagrams(vector<string> &strs) {
  8.         if (strs.size() < 2) {
  9.             return strs;
  10.         }
  12.         vector<string> result;
  13.         vector<bool> visited(strs.size(), false);
  14.         for (int s1 = 0; s1 != strs.size(); ++s1) {
  15.             bool has_anagrams = false;
  16.             for (int s2 = s1 + 1; s2 < strs.size(); ++s2) {
  17.                 if ((!visited[s2]) && isAnagrams(strs[s1], strs[s2])) {
  18.                     result.push_back(strs[s2]);
  19.                     visited[s2] = true;
  20.                     has_anagrams = true;
  21.                 }
  22.             }
  23.             if ((!visited[s1]) && has_anagrams) result.push_back(strs[s1]);
  24.         }
  26.         return result;
  27.     }
  29. private:
  30.     bool isAnagrams(string &s, string &t) {
  31.         if (s.size() != t.size()) {
  32.             return false;
  33.         }
  35.         const int AlphabetNum = 26;
  36.         int letterCount[AlphabetNum] = {0};
  37.         for (int i = 0; i != s.size(); ++i) {
  38.             ++letterCount[s[i] - 'a'];
  39.             --letterCount[t[i] - 'a'];
  40.         }
  41.         for (int i = 0; i != t.size(); ++i) {
  42.             if (letterCount[t[i] - 'a'] < 0) {
  43.                 return false;
  44.             }
  45.         }
  47.         return true;
  48.     }
  49. };

源码分析

  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).

题解2 - 排序 + hashmap

在题 Two Strings Are Anagrams 中曾介绍过使用排序和 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

C++ - lintcode

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param strs: A list of strings
  5.      * @return: A list of strings
  6.      */
  7.     vector<string> anagrams(vector<string> &strs) {
  8.         unordered_map<string, int> hash;
  10.         for (int i = 0; i < strs.size(); i++) {
  11.             string str = strs[i];
  12.             sort(str.begin(), str.end());
  13.             ++hash[str];
  14.         }
  16.         vector<string> result;
  17.         for (int i = 0; i < strs.size(); i++) {
  18.             string str = strs[i];
  19.             sort(str.begin(), str.end());
  20.             if (hash[str] > 1) {
  21.                 result.push_back(strs[i]);
  22.             }
  23.         }
  25.         return result;
  26.     }
  27. };

Java - leetcode

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

源码分析

建立 key 为字符串，value 为相应计数器的hashmap, unordered_map为 C++ 11中引入的哈希表数据结构[^unordered_map], 这种新的数据结构和之前的 map 有所区别，详见[^map-unordered_map]。

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

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

复杂度分析

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

Reference