LeetCode[Hash Table]: Anagrams

LeetCode[Hash Table]: Anagrams

Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.

思路：對每一個單詞的所有字母按照字典順序排序，排序結果作為key，所有具有相同key的單詞組合在一起成為一個Anagram group。最後返回所有的Anagram group。

class Solution {
public:
    vector anagrams(vector &strs) {
        vector result;

        unordered_map> dict;
        for (auto word : strs)
            dict[getLetters(word)].push_back(word);

        for (auto wordGroup : dict)
            if (wordGroup.second.size() > 1)
                result.insert(result.end(), wordGroup.second.begin(), wordGroup.second.end());

        return result;
    }

private:
    string getLetters(string word) {
        string letters;
        for    (auto letter : word) {
            int i;
            for (i = 0; i < letters.size(); ++i)
                if (letters[i] > letter)
                    break;

            letters.insert(letters.begin() + i, letter);
        }

        return letters;
    }
};

上面的解法中，對每一個單詞按照字典順序排序采用自己寫的插入排序算法，也可以采用中的sort函數。

class Solution {
public:
    vector anagrams(vector &strs) {
        vector result;

        unordered_map> dict;
        for (auto word : strs){
            string tmp = word;
            sort(tmp.begin(), tmp.end());
            dict[tmp].push_back(word);
        }

        for (auto group : dict)
            if (group.second.size() > 1)
                result.insert(result.end(), group.second.begin(), group.second.end());

        return result;
    }
};