题目链接：Anagrams
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
这道题的要求是给定字符串数组，返回能构成异构的所有字符串。
anagram，即异构，意思是指由颠倒字母顺序组成的单词，比如“live”颠倒字母顺序会变成“evil”（不好好活着就会成恶魔），因此“live”和“evil”就构成异构。异构构词法有一个特点：单词里的字母的种类和数目没有改变，只是改变了字母的排列顺序。
知道了题意，那么思路就来了，对每个字符串hash，然后返回hash值数目超过1的所有字符串。在hash时，字符串中字母顺序不同的字符串应该有同样的hash值，因此可以考虑先对字符串的字符排序。
这里使用map进行hash处理，key为排序后的字符串，value为字符串的第一次出现的位置，如果重复出现，则value置为-1。这样当key第一次出现时，记录字符串的位置到value中，而当同样的key又出现的时候，将之前的字符串也记录下来。
时间复杂度：O(nllogl)（l为字符串长度）
空间复杂度：O(n*l)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution
{
public:
vector<string> anagrams(vector<string> &strs)
{
vector<string> vs;
map<string, int> m;
for(int i = 0; i < strs.size(); ++ i)
{
string s = strs[i];
sort(s.begin(), s.end());
if(m.find(s) == m.end())
m[s] = i;
else
{
if(m[s] >= 0)
{
vs.push_back(strs[m[s]]);
m[s] = -1;
}
vs.push_back(strs[i]);
}
}
return vs;
}
};
考虑到是字符串中的子串进行排序，因此，可以按计数排序的思路，将排序的时间复杂度降为O(l)。
时间复杂度：O(n*l)（l为字符串长度）
空间复杂度：O(n*l)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution
{
public:
vector<string> anagrams(vector<string> &strs)
{
vector<string> vs;
unordered_map<string, int> m;
for(int i = 0; i < strs.size(); ++ i)
{
string s = sortStr(strs[i]);
if(m.find(s) == m.end())
m[s] = i;
else
{
if(m[s] >= 0)
{
vs.push_back(strs[m[s]]);
m[s] = -1;
}
vs.push_back(strs[i]);
}
}
return vs;
}
private:
string sortStr(string &s)
{
vector<int> vi(26, 0);
for(int i = 0; i < s.size(); ++ i)
++ vi[s[i] - 'a'];
string res = "";
for(int i = 0; i < vi.size(); ++ i)
while(vi[i] --)
res += (char)(i + 'a');
return res;
}
};