Problem: 49. 字母異位詞分組
字母異位詞的定義是：兩個單詞的字母組成一樣，但順序可以不同，比如 eat、tea 和 ate 就是一個組的。
思路
將每個字符串按字母排序，把排序后的字符串作為 key，相同 key 的放在一個 list 中，最終將這些 list 返回。
解題過程
-
核心思想：
? 字母異位詞排序后是相同的字符串。
? 我們可以將每個字符串排序后，作為 map 的 key，原始字符串作為 value。
? 如果多個字符串排序后結果一致，說明它們屬于同一個“異位詞”組。
-
實現方式：
（1）使用一個 HashMap<String, List>：
- key：排序后的字符串（唯一標識一組異位詞）。
- value：原始字符串組成的列表。
（2）遍歷輸入數組 strs：
- 每個字符串轉為字符數組并排序。
- 把排序后的字符串作為 key，根據 key 獲取已有的 list，沒有則新建。
- 把原字符串添加到對應的 list 中。
（3）最后返回 map 中所有的 value（即每組異位詞）。
復雜度
-
時間復雜度：O(n * k log k)
-
- 是字符串個數
-
- 是字符串最大長度（每次排序耗時 O(k log k)）
-
空間復雜度：O(n * k)
-
- 用于存儲結果列表和中間 map
Code
class Solution {public List<List<String>> groupAnagrams(String[] strs) {HashMap<String, List<String>> map = new HashMap<>();for(String str : strs) {// 1. 將每個單詞轉成 char 數組，并且進行排序char[] temp = str.toCharArray();Arrays.sort(temp);String key = new String(temp);// 2. 排序后的值作為 key，原始值作為 List 集合中的 value。相同的 key 存在同一個 List<String> 中List<String> list = map.getOrDefault(key, new ArrayList<>());list.add(str);map.put(key, list);}return new ArrayList<>(map.values());}
}
