LeetCode49 字母異位詞分組

在這篇博客中，我們將探討 LeetCode 上的一道經典算法問題：字母異位詞分組。這個問題要求將給定的字符串數(shù)組中的字母異位詞組合在一起，并以任意順序返回結果列表。

問題描述

給定一個字符串數(shù)組 strs，要求將其中的字母異位詞組合在一起，并返回組合后的結果列表。字母異位詞是由重新排列源單詞的所有字母得到的新單詞。

解決方案思路

我們可以使用哈希表來解決這個問題。具體的思路如下：

1. 創(chuàng)建一個哈希表 unordered_map<string, vector<string>>，用于存儲排序后的字符串和對應的原始字符串數(shù)組。
2. 遍歷輸入的字符串數(shù)組 strs，對于每個字符串 str：
   • 將其排序后得到的字符串 sorted_str 作為鍵，原始字符串 str 添加到哈希表中相應鍵對應的向量中。
3. 遍歷哈希表，將每個鍵對應的值（即原始字符串數(shù)組）放入結果列表中。

下面是用 C++ 實現(xiàn)的解決方案：

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {// 創(chuàng)建哈希表unordered_map<string, vector<string>> M;// 遍歷字符串數(shù)組for (string str : strs) {// 將字符串排序string sorted_str = str;sort(sorted_str.begin(), sorted_str.end());// 將排序后的字符串作為鍵，將原始字符串添加到對應的向量中M[sorted_str].push_back(str);}// 將哈希表中的結果轉換為答案列表vector<vector<string>> ans;for (auto pair : M) {ans.push_back(pair.second);}return ans;}
};

復雜度分析

時間復雜度

• 排序字符串： 對于給定的每個字符串，需要將其排序，時間復雜度為 $O(k\log k)$，其中 $k$ 是字符串的最大長度。
• 遍歷字符串數(shù)組： 遍歷整個字符串數(shù)組并將其添加到哈希表中，時間復雜度為 $O(n)$，其中 $n$ 是字符串數(shù)組的大小。
• 構建結果列表： 遍歷哈希表并構建結果列表，時間復雜度為 $O(m)$，其中 $m$ 是哈希表中鍵值對的數(shù)量。

綜上所述，總體時間復雜度為 $O(n?k\log k+m)$。

空間復雜度

• 哈希表存儲： 使用了哈希表存儲每個排好序的字符串及其對應的源字符串數(shù)組，空間復雜度為 $O(n)$，其中 $n$ 是字符串數(shù)組的大小。

因此，該算法的空間復雜度為 $O(n)$。

通過以上分析，我們可以看到，這種基于哈希表的解決方案在時間和空間復雜度上都具有較好的性能，能夠高效地解決字母異位詞分組的問題。

總結

字母異位詞分組問題可以通過使用哈希表來有效地解決。通過對每個字符串進行排序，并將排序后的字符串作為鍵，我們可以將具有相同字母組成的單詞分組在一起。最終，我們將哈希表中的結果轉換為答案列表，即得到了按要求分組的字母異位詞列表。