在這篇博客中，我們將詳細解析如何使用 Java 代碼來解決 字母異位詞分組這個經典的算法問題。我們會逐步分析代碼邏輯，并探討其時間復雜度及優化思路。

題目描述

給定一個字符串數組 strs，請將字母異位詞組合在一起。字母異位詞是指由相同字母組成但順序不同的字符串。例如：

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

代碼實現

我們可以使用 哈希表 + 排序??來解決這個問題，代碼如下：

class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 創建一個哈希表，用于存儲歸類后的異位詞組Map<String, List<String>> map = new HashMap<>();// 遍歷字符串數組for (int i = 0; i < strs.length; i++) {String s = strs[i];// 將字符串轉換為字符數組，并排序char[] ch = s.toCharArray();Arrays.sort(ch);// 將排序后的字符數組轉換回字符串作為哈希表的 keyString key = new String(ch);// 獲取當前 key 對應的列表（如果不存在則創建新的列表）List<String> li = map.getOrDefault(key, new ArrayList<>());// 將當前字符串加入列表li.add(s);// 更新哈希表map.put(key, li);}// 返回哈希表中所有值組成的列表return new ArrayList<>(map.values());}
}

代碼解析

1. 使用哈希表進行分組

• 核心思想：字母異位詞排序后得到的字符串是相同的，我們可以利用這個特性，將其作為哈希表 map 的鍵（key），對應的值（value）是屬于該類的字符串列表。

• 哈希表結構：

  {"aet": ["eat", "tea", "ate"],"ant": ["tan", "nat"],"abt": ["bat"]
  }
  

2. 遍歷字符串數組

• 遍歷輸入的 strs 數組，對每個字符串：

  1. 將其轉換為字符數組并排序。

  2. 排序后的結果作為 key，存入 map 中。

  3. 若 key 已存在，則添加到對應的 List；若不存在，則新建 List。

3. 返回最終結果

• map.values() 存儲了所有的分組，因此我們返回 new ArrayList<>(map.values())。

時間復雜度分析

1. 排序時間復雜度

• 每個字符串需要排序，假設字符串的最大長度為 K，那么排序的時間復雜度是 O(K log K)。

2. 遍歷字符串數組

• 假設字符串數組的大小是 N，那么遍歷 N 個字符串的時間復雜度是 O(N)。

3. 總體時間復雜度

• 由于我們需要對 N 個字符串進行排序，每個排序的復雜度為 O(K log K)，總的時間復雜度為：

  O(N * K log K)
  

  其中：

  • N 是字符串數組的大小

  • K 是字符串的平均長度

優化思路

1. 使用字符計數代替排序

   • 我們可以用長度為 26 的整數數組（表示 a-z 的頻次）作為 key，而不是排序后的字符串。

   • 這樣可以避免 O(K log K) 的排序時間，將其優化為 O(K)。

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String s : strs) {// 統計字符出現頻率int[] count = new int[26];for (char c : s.toCharArray()) {count[c - 'a']++;}// 生成唯一的 keyString key = Arrays.toString(count);// 存入哈希表map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);}return new ArrayList<>(map.values());}
}

新方法的時間復雜度

• 由于 Arrays.toString(count) 生成的 key 長度固定為 26（英文字母個數），其構建的時間復雜度是 O(1)。

• 整體時間復雜度降低為 O(NK)，比 O(NK log K) 更高效。

總結

• 本文詳細解析了 字母異位詞分組 問題，并使用 排序 + 哈希表 進行求解。

• 時間復雜度為 O(NK log K)。

• 通過 字符計數法，可以進一步優化到 O(NK)。

• 這是一道典型的哈希表應用題目，考察了字符串處理和數據結構的使用。

希望本文能幫助你更好地理解該問題！如果有任何疑問或優化建議，歡迎交流討論！🎯