Leetcode

字母异位词

所谓的字母异位词，其意思是不同的单词本质上只是相同的单词打乱顺序，这类单词就是字母异位词。

对于一部分同学来说，可能并不清楚字符串string在c++中是个容器，而容器基本上都是可以对内容进行排序的。
所以字母异位词的打乱顺序在排序面前形同虚设。
在知道这个知识点以后，我们理所当然地可以想到，对每一个字符串进行排序，排完序之后如果是一样的，那这些字符串就是我们需要的答案。

1
sort(str.size(), str.end());

话不多说，直接开始遍历。

1
2
3
for (auto &str: strs) {
  
}

这种遍历方式对于初学者来说可能不好理解，如果有疑问可以在discussion中评论，暂时你只需要知道auto是c++自动推断变量类型的工具，而for循环中就是把strs数组中的每一个字符串拿出来，这个字符串叫str。
当我们遍历得到当前的字符串时，千万不能直接对其排序，因为我们最终输出的答案还得是排序之前被打乱过顺序的字符串。
所以我们找一个临时变量x来保存字符串内容。

1
2
3
4
for (auto &str: strs) {
		auto x = str;
  	sort(x.begin(), x.end());
}

接下来就是初学者比较难想的点：为什么要用哈希表?
在两数之和这道题目里我们已经讲过，哈希表的优点就是高效查找之前遍历过的值，并且可以保存二元组，第一个优点很好理解，但这一题我们需要保存什么样的二元组呢？
让我们来理一下思路：我们排完序得到的字符串结果是什么？是一个范例，所有排完序符合这个范例的都应该隶属于这个范例，成为结果字符串数组的一部分。
那么范例–对应字符串数组就是我们需要存储在哈希表里的二元组。
x—-范例
str—对应字符串数组的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
unordered_map<string, vector<string>> heap;
for (auto &str: strs) {
		auto x = str;
		sort(x.begin(), x.end());
		heap[x].push_back(str);
}

vector<vector<string>> res;//答案数组
//遍历哈希表，把答案分组塞入答案数组
for (auto &item: heap) {
		res.push_back(item);
}
return res;

关于语法的问题，欢迎初学的同学来问，有讲的不清楚和错误的地方欢迎指正~
感谢。