题目链接

注意点

字母都是小写的

解法

解法一：用一个字符串表示strs[i]中出现的字母，比如：abc->111000000000000000000000000、aab->210000000000000000000000000。同时用map保存hash与vector的下标对应关系。时间复杂度O(n)

class Solution {

public:

    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        vector<vector<string>> ret;

        map<string,int> m;

        if(strs.size() == 0) return ret;

        int i,j,n = strs.size();

        for(i = 0;i < n;i++)

        {

            string hash = "000000000000000000000000000";

            for(j = 0;j < strs[i].size();j++)

            {

                hash[strs[i][j] - 'a']++;

            }

            cout << strs[i] << " " << hash << endl;

            if(m.find(hash) == m.end())

            {

                vector<string> temp{strs[i]};

                ret.push_back(temp);

                m[hash] = ret.size()-1;

            }

            else

            {

                int index = m[hash];

                ret[index].push_back(strs[i]);

            }

        }

        return ret;

    }

};

解法二：abc与bac的区别只在于顺序不同，因此，只要对strs[i]排序之后进行比较即可。时间复杂度O(nlogn)。

class Solution {

public:

    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        vector<vector<string>> ret;

        unordered_map<string, vector<string>> m;

        for (string str : strs) {

            string t = str;

            sort(t.begin(), t.end());

            m[t].push_back(str);

        }

        for (auto a : m) {

            ret.push_back(a.second);

        }

        return ret;

    }

};

小结

解法二的时间复杂度更高，但是所花时间更少...

巴特西

Group Anagrams - LeetCode

题目链接

注意点

解法

小结

最新文章

热门文章