原題

LintCode 171. Anagrams

Description

Given an array of strings, return all groups of strings that are anagrams.

Notice

All inputs will be in lower-case

Example

Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].

Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].

解題

題意是在一組字符串中，找到所有出現(xiàn)兩次及以上的亂序字符串。

思路是，實(shí)現(xiàn)一個(gè)映射，使得對(duì)于任意相同但亂序的字符串，映射后的值相同。
這里的實(shí)現(xiàn)是，將輸入的字符串轉(zhuǎn)為“字母+數(shù)字”的形式，其中數(shù)字為字母在字符串中出現(xiàn)的次數(shù)。例如“aabc”和“abca”的映射結(jié)果都是“a2b1c1”。

只需要遍歷一次數(shù)組，然后將所有的字符串都進(jìn)行一次映射，并將映射值相同的字符串放在同一個(gè)數(shù)組內(nèi)。最后將所有大小超過(guò)1的數(shù)組組合起來(lái)即可。

代碼

class Solution {
public:
    /*
    * @param strs: A list of strings
    * @return: A list of strings
    */
    vector<string> anagrams(vector<string> &strs) {
        // write your code here
        map<string, vector<string>> m;
        vector<string> res;
        for (auto &str : strs) {
            int alphabet[26] = { 0 };
            for (auto c : str) {
                alphabet[c - 'a']++;
            }
            string key;
            key.reserve(10);
            for (int i = 0; i < 26; i++) {
                if (alphabet[i]) {
                    key += char(i + 'a');
                    key += alphabet[i];
                }
            }
            auto it = m.find(key);
            if (it == m.end()) {
                m.insert({ key, vector<string>{str} });
            } else {
                it->second.push_back(str);
            }
        }
        for (auto &p : m) {
            if (p.second.size() > 1) {
                res.insert(res.end(), p.second.begin(), p.second.end());
            }
        }
        return res;
    }
};