100道面試必會算法-31-字母異位詞分組
給你一個字符串數組，請你將 字母異位詞 組合在一起。可以按任意順序返回結果列表。
字母異位詞 是由重新排列源單詞的所有字母得到的一個新單詞。
示例 1:
輸入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
輸入: strs = [""]
輸出: [[""]]
示例 3:
輸入: strs = ["a"]
輸出: [["a"]]
解題思路
遍歷字符串數組
strs，對每個字符串進行處理：
- 將字符串轉換為字符數組并進行排序。
- 將排序后的字符數組轉換為字符串，作為鍵。
- 將原始字符串作為值，存儲在相應鍵的列表中。
最終將所有的值（即分組好的字母異位詞列表）轉換為 ArrayList 并返回。
代碼
class Solution {// 定義一個方法用于對字符串數組中的字符串進行分組public List<List<String>> groupAnagrams(String[] strs) {// 創建一個新的列表，其中包含根據相同字符組成的字符串對字符串數組進行分組的結果return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str->{// 將字符串轉換為字符數組，并對字符數組進行排序char[] array=str.toCharArray();Arrays.sort(array);return new String(array);})).values());}
}
詳細步驟
-
轉換為流：
Arrays.stream(strs)將字符串數組
strs轉換為一個流（Stream），以便使用流的操作來處理數據。 -
分組操作：
Collectors.groupingBy(str -> {char[] array = str.toCharArray();Arrays.sort(array);return new String(array); })使用
Collectors.groupingBy將字符串按照排序后的字符數組進行分組。具體步驟如下：- 將字符串轉換為字符數組
char[] array = str.toCharArray();。 - 對字符數組進行排序
Arrays.sort(array);。 - 將排序后的字符數組轉換回字符串
return new String(array);，作為分組的鍵。
- 將字符串轉換為字符數組
-
轉換為列表：
new ArrayList<>(...values())最后，將分組后的值（即字母異位詞列表）轉換為
ArrayList，并返回結果。
優點
- 簡潔性：使用 Java Stream API 和 Collectors 使代碼簡潔明了。
- 效率：排序操作的時間復雜度為 O(n log n)，遍歷和分組操作的時間復雜度為 O(n)，總體來說效率較高。
總結
通過對字符串排序并利用 Map 進行分組，巧妙地將字母異位詞歸為一類。最終，使用 Java Stream API 將結果整理為所需的列表形式，代碼簡潔高效，適用于大多數情況下的字母異位詞分組問題。
)
