# Anagrams ### Source - leetcode: [Anagrams | LeetCode OJ](https://leetcode.com/problems/anagrams/) - lintcode: [(171) Anagrams](http://www.lintcode.com/en/problem/anagrams/) ~~~ Given an array of strings, return all groups of strings that are anagrams. Example Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"]. Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"]. Note All inputs will be in lower-case ~~~ ### 題解1 - 雙重`for`循環([TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。")) 題 [Two Strings Are Anagrams](http://algorithm.yuanbin.me/zh-cn/string/two_strings_are_anagrams.html) 的升級版，容易想到的方法為使用雙重`for`循環兩兩判斷字符串數組是否互為變位字符串。但顯然此法的時間復雜度較高。還需要 O(n)O(n)O(n) 的數組來記錄字符串是否被加入到最終結果中。 ### C++ ~~~ class Solution { public: /** * @param strs: A list of strings * @return: A list of strings */ vector<string> anagrams(vector<string> &strs) { if (strs.size() < 2) { return strs; } vector<string> result; vector<bool> visited(strs.size(), false); for (int s1 = 0; s1 != strs.size(); ++s1) { bool has_anagrams = false; for (int s2 = s1 + 1; s2 < strs.size(); ++s2) { if ((!visited[s2]) && isAnagrams(strs[s1], strs[s2])) { result.push_back(strs[s2]); visited[s2] = true; has_anagrams = true; } } if ((!visited[s1]) && has_anagrams) result.push_back(strs[s1]); } return result; } private: bool isAnagrams(string &s, string &t) { if (s.size() != t.size()) { return false; } const int AlphabetNum = 26; int letterCount[AlphabetNum] = {0}; for (int i = 0; i != s.size(); ++i) { ++letterCount[s[i] - 'a']; --letterCount[t[i] - 'a']; } for (int i = 0; i != t.size(); ++i) { if (letterCount[t[i] - 'a'] < 0) { return false; } } return true; } }; ~~~ ### 源碼分析 1. strs 長度小于等于1時直接返回。 1. 使用與 strs 等長的布爾數組表示其中的字符串是否被添加到最終的返回結果中。 1. 雙重循環遍歷字符串數組，注意去重即可。 1. 私有方法`isAnagrams`用于判斷兩個字符串是否互為變位詞。 ### 復雜度分析 私有方法`isAnagrams`最壞的時間復雜度為 O(2L)O(2L)O(2L), 其中 LLL 為字符串長度。雙重`for`循環時間復雜度近似為 12O(n2)\frac {1}{2} O(n^2)21O(n2), nnn 為給定字符串數組數目。總的時間復雜度近似為 O(n2L)O(n^2 L)O(n2L). 使用了含有26個元素的 int 數組，空間復雜度可認為是 O(1)O(1)O(1). ### 題解2 - 排序 + hashmap 在題 [Two Strings Are Anagrams](http://algorithm.yuanbin.me/zh-cn/string/two_strings_are_anagrams.html) 中曾介紹過使用排序和 hashmap 兩種方法判斷變位詞。這里我們將這兩種方法同時引入！只不過此時的 hashmap 的 key 為字符串，value 為該字符串在 vector 中出現的次數。兩次遍歷字符串數組，第一次遍歷求得排序后的字符串數量，第二次遍歷將排序后相同的字符串取出放入最終結果中。 **leetcode 上此題的 signature 已經更新，需要將 anagrams 按組輸出，稍微麻煩一點點。** ### C++ - lintcode ~~~ class Solution { public: /** * @param strs: A list of strings * @return: A list of strings */ vector<string> anagrams(vector<string> &strs) { unordered_map<string, int> hash; for (int i = 0; i < strs.size(); i++) { string str = strs[i]; sort(str.begin(), str.end()); ++hash[str]; } vector<string> result; for (int i = 0; i < strs.size(); i++) { string str = strs[i]; sort(str.begin(), str.end()); if (hash[str] > 1) { result.push_back(strs[i]); } } return result; } }; ~~~ ### Java - leetcode ~~~ public class Solution { public List<List<String>> groupAnagrams(String[] strs) { List<List<String>> result = new ArrayList<List<String>>(); if (strs == null) return result; // one key to multiple value multiMap Map<String, ArrayList<String>> multiMap = new HashMap<String, ArrayList<String>>(); for (String str : strs) { char[] strChar = str.toCharArray(); Arrays.sort(strChar); String strSorted = String.valueOf(strChar); if (multiMap.containsKey(strSorted)) { ArrayList<String> aList = multiMap.get(strSorted); aList.add(str); multiMap.put(strSorted, aList); } else { ArrayList<String> aList = new ArrayList<String>(); aList.add(str); multiMap.put(strSorted, aList); } } // add List group to result Set<String> keySet = multiMap.keySet(); for (String key : keySet) { ArrayList<String> aList = multiMap.get(key); Collections.sort(aList); result.add(aList); } return result; } } ~~~ ### 源碼分析 建立 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(n)O(n), 對單個字符串排序復雜度近似為 O(LlogL)O(L \log L)O(LlogL). 兩次遍歷字符串數組，故總的時間復雜度近似為 O(nLlogL)O(nL \log L)O(nLlogL). 使用了哈希表，空間復雜度為 O(K)O(K)O(K), 其中 K 為排序后不同的字符串個數。 ### Reference - unordered_map > . [unordered_map - C++ Reference](http://www.cplusplus.com/reference/unordered_map/unordered_map/)[ ?](# "Jump back to footnote [unordered_map] in the text.") - map-unordered_map > . [c++ - Choosing between std::map and std::unordered_map - Stack Overflow](http://stackoverflow.com/questions/3902644/choosing-between-stdmap-and-stdunordered-map)[ ?](# "Jump back to footnote [map-unordered_map] in the text.") - [Anagrams | 九章算法](http://www.jiuzhang.com/solutions/anagrams/)