首页 > 代码库 > 【LeetCode】Anagrams
【LeetCode】Anagrams
Anagrams
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
首先解释一下什么是anagrams：在不考虑顺序的情况下，包含相同字母的字符串组成anagrams
例如：
1、{"eat","ate","tea","coffee"}的anagrams是{"eat","ate","tea"}
2、{"tea","and","ate","eat","dan"}的anagrams是{"tea","ate","eat","and","dan"}
解法一：排序作为key
在具体实现过程中，构造了两张映射表m和exist
m用来对排序过的单词进行快速查找，值(value)为第一个该编码的单词下标。
exist用来记录该排序过的单词是否已存在anagrams中，
如果是，只需要将当前单词装入anagrams；
如果不是，首先要将存放在m中的代表该排序过的单词的第一个单词装入anagrams，再装入当前单词。
class Solution {public: vector<string> anagrams(vector<string> &strs) { map<string, int> m; map<string, bool> exist; vector<string> ret; for(int i = 0; i < strs.size(); i ++) { string cur = strs[i]; sort(cur.begin(),cur.end()); if(m.find(cur) == m.end()) m[cur] = i; else { if(exist.find(cur) == exist.end()) {//if not exist, add the first word exist[cur] = true; ret.push_back(strs[m[cur]]); } ret.push_back(strs[i]); } } return ret; }};
解法二：利用质因数分解
背景：任何一个正整数都可以分解为唯一的质因数乘积：n=2a3b5c7d…
因此n可以用{a,b,c,d}来唯一表示。
对于这个题，我们对a~z每个单词的出现次数作为每个质因数的次幂，
将乘积进行唯一编码，就可以忽略字母顺序了。相同编码的单词组成anagrams。
因为共有小写字母26个，因此我们需要前26个质因数。
在具体实现过程中，我还构造了两张映射表m和exist
m用来对编码进行快速查找，值(value)为第一个该编码的单词下标。
exist用来记录该编码是否已存在anagrams中，
如果是，只需要将当前单词装入anagrams；
如果不是，首先要将存放在m中的代表该编码的第一个单词装入anagrams，再装入当前单词。
class Solution {public: vector<string> anagrams(vector<string> &strs) { vector<long long int> code(strs.size(), 0); CalCode(strs, code); map<long long int, int> m; vector<string> ret; for(int i = 0; i < strs.size(); i ++) { if(m.find(code[i]) == m.end()) m[code[i]] = i; else { ret.push_back(strs[m[code[i]]]); ret.push_back(strs[i]); for(int j = i+1; j < strs.size(); j ++) { if(code[j] == code[i]) { ret.push_back(strs[j]); } } return ret; } } //not found return ret; } void CalCode(vector<string> &strs, vector<long long int> &code) { for(int i = 0; i < strs.size(); i ++) { string cur = strs[i]; vector<int> count(26, 0); //a~z count for(int j = 0; j < cur.size(); j ++) { count[cur[j]-‘a‘] ++; } double prime[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101}; long long result = 1; for(int j = 0; j < 26; j ++) { result *= (long long int)pow(prime[j], count[j]); } code[i] = result; } }};
【LeetCode】Anagrams