C++實(shí)現(xiàn)LeetCode(49.群組錯(cuò)位詞)

更新時(shí)間：2021年07月15日 16:10:04 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(49.群組錯(cuò)位詞),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 49. Group Anagrams 群組錯(cuò)位詞

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

Note:

All inputs will be in lowercase.
The order of your output does not matter.

這道題讓我們?nèi)航M給定字符串集中所有的錯(cuò)位詞，所謂的錯(cuò)位詞就是兩個(gè)字符串中字母出現(xiàn)的次數(shù)都一樣，只是位置不同，比如 abc，bac, cba 等它們就互為錯(cuò)位詞，那么如何判斷兩者是否是錯(cuò)位詞呢，可以發(fā)現(xiàn)如果把錯(cuò)位詞的字符順序重新排列，那么會(huì)得到相同的結(jié)果，所以重新排序是判斷是否互為錯(cuò)位詞的方法，由于錯(cuò)位詞重新排序后都會(huì)得到相同的字符串，以此作為 key，將所有錯(cuò)位詞都保存到字符串?dāng)?shù)組中，建立 key 和當(dāng)前的不同的錯(cuò)位詞集合個(gè)數(shù)之間的映射，這里之所以沒有建立 key 和其隸屬的錯(cuò)位詞集合之間的映射，是用了一個(gè)小 trick，從而避免了最后再將 HashMap 中的集合拷貝到結(jié)果 res 中。當(dāng)檢測到當(dāng)前的單詞不在 HashMap 中，此時(shí)知道這個(gè)單詞將屬于一個(gè)新的錯(cuò)位詞集合，所以將其映射為當(dāng)前的錯(cuò)位詞集合的個(gè)數(shù)，然后在 res 中新增一個(gè)空集合，這樣就可以通過其映射值，直接找到新的錯(cuò)位詞集合的位置，從而將新的單詞存入結(jié)果 res 中，參見代碼如下：

解法一：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, int> m;
        for (string str : strs) {
            string t = str;
            sort(t.begin(), t.end());
            if (!m.count(t)) {
                m[t] = res.size();
                res.push_back({});
            }
            res[m[t]].push_back(str);
        }
        return res;
    }
};

下面這種解法沒有用到排序，用一個(gè)大小為 26 的 int 數(shù)組來統(tǒng)計(jì)每個(gè)單詞中字符出現(xiàn)的次數(shù)，然后將 int 數(shù)組轉(zhuǎn)為一個(gè)唯一的字符串，跟字符串?dāng)?shù)組進(jìn)行映射，這樣就不用給字符串排序了，參見代碼如下：

解法二：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> m;
        for (string str : strs) {
            vector<int> cnt(26);
            string t;
            for (char c : str) ++cnt[c - 'a'];
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] == 0) continue;
                t += string(1, i + 'a') + to_string(cnt[i]);
            }
            m[t].push_back(str);
        }
        for (auto a : m) {
            res.push_back(a.second);
        }
        return res;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(49.群組錯(cuò)位詞)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)群組錯(cuò)位詞內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: