anagrams

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

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

hint: string也能sort!!!!!!

时间复杂度 kn

code

class Solution {
public:    
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    vector<string> anagrams(vector<string> &strs) {
        // write your code here
        vector<string> ret;
        map<string, vector<string>> hash;

        //遍历一遍，对每个字符窜，用他sort后来做key anagram;

        for(string s : strs)
        {
            bool found = false;
            string st = s;
            sort(st.begin(), st.end());

            if(hash.find(st) != hash.end())
            {
                hash[st].push_back(s);
            }
            else
            {
                vector<string> tmp;
                tmp.push_back(s);
                hash[st] = tmp;
            }
        }

        for(auto& kv : hash)
        {
            if(kv.second.size() > 1)
            {
                for(string s : kv.second)
                {
                    ret.push_back(s);
                }
            }
        }

        return ret;
    }
};