49. Group Anagrams - Medium

前往題目

想法

• 回傳包含arraylist的arraylist
• 用hashmap arraylist存放每個詞的hashmap，但這樣會有個問題，假設不是同個詞，那要怎麼新增，用一個temp hashmap嗎@@

思路

兩種主要方式:

1. 把string都sort過，同一個詞一定會排序相同，就可以成功分類，但執行時間是O(m * nlogn)，因為有m個string，sort要花nlogn時間

2. 用hashmap，<String, List<String>>，執行時間是O(m * n)

3. 一個hashmap

4. 疊代全部string，數每個字母有幾個

5. 根據數出來的結果找尋key，沒有就新建，有就加進去

Code

說實話我不懂為何一定要用char[] ca，感覺int[]應該也沒問題啊，但用了就會出錯…

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // Map keyString to word
        Map<String, List<String>> map = new HashMap<>();

        // Loop through each string
        for (String s : strs) {
            // for counting
            char[] ca = new char[26];

            // Count the characters
            for (char c : s.toCharArray()) {
                ca[c - 'a']++;
            }

            String keyStr = String.valueOf(ca);
            if (!map.containsKey(keyStr)) {
                // Init.
                map.put(keyStr, new ArrayList<String>());
            }

            // Store the value
            map.get(keyStr).add(s);

        }
        return new ArrayList<>(map.values());
    }
}

2024/04/21

• 忽略了最重要的點，同一組的字母分佈數量是一樣的