變位詞問題/Anagrams

Question：

• Input： 給定的單詞 + 英文單詞詞典
• Output：輸出該單詞的所有變位詞集合

Solution：

1. 對組成單詞的字母進行各種排列組合，然後在字典中比對
   • 不足：組合結果太多：N！，有很多無效組合
2. 先将單詞與字典中的每個單詞比較長度，如果相同繼續比較字母組合是否相同。
   • 不足：時間複雜度：|V| * N
3. 要想把變位詞歸為一類，必須找出他們共同的标記，是以對每個單詞進行簽名（按字母排序），然後變位詞将具有相同的簽名。
   • 時間複雜度： |V|+|V|∗T排序

代碼實作

leetcode 第49題–Group Anagrams

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector< vector<string> > result;
        vector<string> tmp;
        unordered_map<string, vector<int> > map;
        for(int i=; i<strs.size(); i++) {
            string key = strs[i];
            sort(key.begin(), key.end());
            map[key].push_back(i);
        }
        for(unordered_map<string, vector<int> >::iterator it = map.begin(); it!=map.end(); it++) {
            vector<int> index = (*it).second;
            for(vector<int>::iterator it = index.begin(); it!=index.end(); it++) {
                  tmp.push_back(strs[*it]);
            }
            sort(tmp.begin(), tmp.end());
            result.push_back(tmp);
            tmp.clear();
        }
        return result;
    }
};