同字符词语分组
已知一组字符串，将所有anagram(由颠倒字母顺序而构成的字)放到一起输出。 例如:["eat", "tea", "tan", "ate", "nat", "bat"] 返回:[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ] LeetCode 49. Group Anagrams
思考
anagram分组: 若某两个字符串，出现的各个字符数相同， 则它们应该为同一分组。 例如:["eat", "tea", "tan", "ate", "nat", "bat"] 返回:[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]
方法一：
哈 希 表 以 内 部 进 行 排 序 的 各 个 单 词 为 key ， 以 字 符 串 向 量 (vector<string>)为value，存储各个字符数量相同的字符串(anagram)。
设置字符串到字符串向量的哈希表anagram，遍历字符串向量strs中的 单词strs[i]: 1)设置临时变量str = strs[i]，对str进行排序。 2)若str未出现在anagram中，设置str到一个空字符串向量的映射。 3)将strs[i]添加至字符串向量anagram[str]中。 遍历哈希表anagram，将全部key对应的value push至最终结果中。
class Solution{
public:
std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string> & strs){
std::map<std::string, std::vector<std::string>> anagram;
//内部进行排序的各个单词为key，以字符串向量（vector<string>）为value，存储各个字符数量相同的字符串（anagram）
std::vector<std::vector<std::string>> result;//存储最终的结果
for(int i = 0; i < strs.size(); i++){
std:: string str = strs[i];
std::sort(str.begin(), str.end());//对str内部进行排序
if(anagram.find(str) == anagram.end){//无法在哈希表中找打str
std::vector<std::string> item;
anagram[str] = item;
}
anagram[str].push_back(strs[i]);
}
std::map<std::string, std::vector<std::string>> :: iterator it;
for(int = anagram.begin(); it != anagram.end(); i++){
result.push_back((*it).second);
}
return result;
}
};方法二
哈希表以26个字母的字符数量(一个长度为26的vector，统计单词中各个字 符的数量)为key，以字符串向量(vector<string>)为value，存储各个字 符数量相同的字符串(anagram)。
算法设计 设置vector到字符串向量的哈希表anagram，遍历字符串向量strs中的 单词strs[i]: 1)统计strs[i]中的各个字符数量，存储至vec。 2)若vec未出现在anagram中，设置vec到一个空字符串向量的映射。 3)将strs[i]添加至字符串向量anagram[vec]中。 遍历哈希表anagram，将全部key对应的value push至最终结果中。
//将字符串str中的各个字符数量进行统计，存储至vec
void change_to_vector(std::string & str, std::vector<int> & vec){
for(int i = 0; i < 26; i++){
vec.push_back(0);
}
for(int i= 0; i < str.length(); i++){
vec[str[i] - 'a']++
}
}
class Solution{
public:
std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string> & strs){
std::map<std::vector<int>, std::vector<std::string>> anagram;
std::vector<std::vector<std::string>> result;
for(int i =0; i < strs.size(); i++){
std::vector<int> vec;
change_to_vec(strs[i], vec);
if(anagrams.find(vec) == anagram.end()){
std::vector<std::string> item;
anagram[str[i]] = item;
}
anagram[vec].push_back(strs[i]);
}
std::map<std::vector<int>>,std::vector<std::string> :: iterator it;
for(it = anagram.begin(); it != anagram.end(); it++){
result.push_back((* it).second);
}
return result;
}
};腾讯云开发者
