【LeetCode】49. Anagrams (2 solutions)

Anagrams

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

Note: All inputs will be in lower-case.

首先解释一下什么是anagrams：在不考虑顺序的情况下，包含相同字母的字符串组成anagrams

例如：

1、{"eat","ate","tea","coffee"}的anagrams是{"eat","ate","tea"}

2、{"tea","and","ate","eat","dan"}的anagrams是{"tea","ate","eat","and","dan"}

解法一：排序之后的string作为key

在具体实现过程中，构造了两张映射表dict和exist

dict用来对排序过的单词进行快速查找，值(value)为第一个该编码的单词下标。

exist用来记录该排序过的单词是否已存在anagrams中，

如果是，只需要将当前单词装入anagrams；

如果不是，首先要将存放在m中的代表该排序过的单词的第一个单词装入anagrams，再装入当前单词。

class Solution {

public:

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

        vector<string> ret;

        unordered_map<string, int> dict;

        unordered_map<string, bool> exist;

        for(int i = ; i < strs.size(); i ++)

        {

            string temp = strs[i];

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

            if(dict.find(temp) == dict.end())

                dict[temp] = i;

            else

            {//find anagrams

                if(exist[strs[dict[temp]]] == false)

                {

                    ret.push_back(strs[dict[temp]]);

                    exist[strs[dict[temp]]] = true;

                }

                ret.push_back(strs[i]);

                exist[strs[i]] = true;

            }

        }

        return ret;

    }

};

解法二：利用质因数分解

背景：任何一个正整数都可以分解为唯一的质因数乘积：n=2^a3^b5^c7^d…

因此n可以用{a,b,c,d}来唯一表示。

对于这个题，我们对a~z每个单词的出现次数作为每个质因数的次幂，

将乘积进行唯一编码，就可以忽略字母顺序了。相同编码的单词组成anagrams。

因为共有小写字母26个，因此我们需要前26个质因数。

在具体实现过程中，我还构造了两张映射表m和exist

dict用来对编码进行快速查找，值(value)为第一个该编码的单词下标。

exist用来记录该编码是否已存在anagrams中，

如果是，只需要将当前单词装入anagrams；

如果不是，首先要将存放在dict中的代表该编码的第一个单词装入anagrams，再装入当前单词。

class Solution {

public:

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

        vector<string> ret;

        vector<long long int> code(strs.size(), );

        CalCode(strs, code);

        map<long long int, int> dict;

        map<string, bool> exist;

        for(int i = ; i < strs.size(); i ++)

        {

            if(dict.find(code[i]) == dict.end())

                dict[code[i]] = i;

            else

            {

                if(exist[strs[dict[code[i]]]] == false)

                {

                    exist[strs[dict[code[i]]]] = true;

                    ret.push_back(strs[dict[code[i]]]);

                }

                exist[strs[i]] = true;

                ret.push_back(strs[i]);

            }

        }

        return ret;

    }

    void CalCode(vector<string> &strs, vector<long long int> &code)

    {

        for(int i = ; i < strs.size(); i ++)

        {

            string cur = strs[i];

            vector<int> count(, ); //a~z count

            for(int j = ; j < cur.size(); j ++)

            {

                count[cur[j]-'a'] ++;

            }

            double prime[] = {,,,,,,,,,,,,,,,,,,,,,,,,,};

            long long result = ;

            for(int j = ; j < ; j ++)

            {

               result *= (long long int)pow(prime[j], count[j]);

            }

            code[i] = result;

        }

    }

};

巴特西

【LeetCode】49. Anagrams (2 solutions)

最新文章

热门文章