171. Anagrams【medium】

Given an array of strings, return all groups of strings that are anagrams.

Notice

All inputs will be in lower-case

Example

Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].

Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].

Challenge

What is Anagram?
- Two strings are anagram if they can be the same after change the order of characters.

解法一：

 1 class Solution {
 2 public:    
 3     /**
 4      * @param strs: A list of strings
 5      * @return: A list of strings
 6      */
 7     string getSortedString(string &str) {
 8         static int count[26];
 9         for (int i = 0; i < 26; i++) {
10             count[i] = 0;
11         }
12         for (int i = 0; i < str.length(); i++) {
13             count[str[i] - 'a']++;
14         }
15         
16         string sorted_str = "";
17         for (int i = 0; i < 26; i++) {
18             for (int j = 0; j < count[i]; j++) {
19                 sorted_str = sorted_str + (char)('a' + i);
20             }
21         }
22         return sorted_str;
23     }
24     
25     vector<string> anagrams(vector<string> &strs) {
26         unordered_map<string, int> hash;
27         
28         for (int i = 0; i < strs.size(); i++) {
29             string str = getSortedString(strs[i]);
30             if (hash.find(str) == hash.end()) {
31                 hash[str] = 1;
32             } else {
33                 hash[str] = hash[str] + 1;
34             }
35         }
36         
37         vector<string> result;
38         for (int i = 0; i < strs.size(); i++) {
39             string str = getSortedString(strs[i]);
40             if (hash.find(str) == hash.end()) {
41                 continue;
42             } else {
43                 if (hash[str] > 1) {
44                     result.push_back(strs[i]);
45                 }
46             }
47         }
48         return result;
49     }
50 };

手动实现了字符串的排序，有些复杂，参考@NineChapter 的代码

解法二：

 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         int size = strs.size(), i = 0;
 9         if (size <= 0) {
10             return vector<string>();
11         }
12 
13         vector<string> result;
14         map<string, int> hash;
15         for (i = 0; i < size; i++) {
16             string temp = strs[i];
17             sort(temp.begin(), temp.end());
18             hash[temp]++;
19         }
20         for (i = 0; i < size; i++) {
21             string temp = strs[i];
22             sort(temp.begin(), temp.end());
23             if (hash[temp] > 1) {
24                 result.push_back(strs[i]);
25             }
26         }
27         return result;
28     }
29 };

直接用STL的sort函数搞