【Leetcode 筆記】 49. Group Anagrams

題目解釋

前置題目：【Leetcode 筆記】 242. Valid Anagram

字謎 (Anagram) 是透過重新排列不同 word 的 character 而形成的新 word，通常只使用一次所有原始字母。

你必須把有相同 anagram 的 elements 組合起來放到同一個 sub list 中。

範例

• 輸入: strs = ["eat","tea","tan","ate","nat","bat"]
• 輸出: [["bat"],["nat","tan"],["ate","eat","tea"]]

nat 重新排列之後可以變成跟 tan 一樣的詞，所以 group 在一起。

最佳解法

如果看過前置題目 【Leetcode 筆記】 242. Valid Anagram 就會簡單很多，
以 sort 過的做為 key，再將所有變體放進對應 key 中的 list，最後只回傳 dict.values() 就好了。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = dict()

        for s in strs:
            key = "".join(sorted(s))
            if key not in groups:
                groups[key] = [s]
            else:
                groups[key].append(s)

        return groups.values()

時間複雜度

O(n)，雖然 sort 只需要 O(nlogn) 但是我們必須 traverse 整個 array 才能解決這個問題。

冷知識

如果真的想深究 python 底層用什麼 sort algorithm 的話，
可以參考這篇 Quicksort, Timsort, Powersort，python 3.11 後從 Timsort 改為 Powersort，
兩種演算法都結合並改善了 Merge Sort 需要 O(n) 空間以及 Quick Sort 不 stable 的特性。

空間複雜度

O(n)，groups 的大小。

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26