原题

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"].

解题

题意是在一组字符串中，找到所有出现两次及以上的乱序字符串。

思路是，实现一个映射，使得对于任意相同但乱序的字符串，映射后的值相同。
这里的实现是，将输入的字符串转为“字母+数字”的形式，其中数字为字母在字符串中出现的次数。例如“aabc”和“abca”的映射结果都是“a2b1c1”。

只需要遍历一次数组，然后将所有的字符串都进行一次映射，并将映射值相同的字符串放在同一个数组内。最后将所有大小超过1的数组组合起来即可。

代码

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;
    }
};