原文題目

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

題目摘要

1. 給定一個字串陣列 strs，將所有的字母異位詞分組在一起，回傳的結果順序可以是任意的。
2. 異位詞指由相同字母重排列形成的字符串

Example 1:

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

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

Explanation:

There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

解題思路

1. 使用 HashMap 進行分組：
   • 目標是將字母異位詞放在同一組。字母異位詞是由相同字母組成但順序不同的字串，因此我們可以將每個字串排序後，使用排序後的結果作為 HashMap 的鍵（key）。
   • 初始化一個 HashMap<String, List<String>>，用於將排序後的字串作為鍵，對應的值為字母異位詞的原始字串列表。
2. 遍歷所有字串並排序：
   • 對於輸入的每個字串，先將其轉換為字符陣列並排序，這樣相同字母組成的字串在排序後都會變成相同的字符序列。
   • 排序後的字符陣列再轉換回字串，作為 HashMap 的鍵。
3. 將字串添加到對應的列表：
   • 檢查 HashMap 中是否已經存在排序後的字串作為鍵。如果沒有，則創建一個新的列表作為值。
   • 將原始的字串添加到對應的列表中，這樣每個字母異位詞都會被放入相同的列表。
4. 回傳結果：
   • 最後將 HashMap 中所有分組好的值收集起來，並以列表的形式回傳。

程式碼

class Solution { 
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>(); //設立一個HashMap來存放結果
        
        //遍歷所有字串
        for (String str : strs) {
            //將字串轉成字符陣列並排序
            char[] charArray = str.toCharArray(); 
            Arrays.sort(charArray);

            // 排序後的字串作為 key
            String sortedStr = new String(charArray);

            //如果map中沒有這個key，則創建一個新的列表
            if (!map.containsKey(sortedStr)) {
                map.put(sortedStr, new ArrayList<>());
            }
            
            map.get(sortedStr).add(str); //將原始字串加入到對應的列表中
        }
        
        return new ArrayList<>(map.values()); //回傳map中所有分組好的字串列表值
    }
}

結論
這道題目的核心在於理解異位詞的特性，即兩個字串若由相同字母組成，即使順序不同，也屬於同一組。因此，將每個字串進行排序，能將異位詞轉換為相同的形式，這樣我們就能輕鬆分組。這裡我使用 HashMap 來進行分組，這個方法能夠快速找到異位詞組合的標識。每當我們遍歷一個字串並對其排序時，這個排序後的字串作為 HashMap 的鍵，對應的值則是所有屬於這個異位詞組的字串。這樣的結構可以確保每個異位詞組都能準確地被放入同一個列表中，並且在查找和添加元素時的時間複雜度保持較低。