【Leetcode 筆記】 242. Valid Anagram

題目解釋

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

範例

• 輸入: s = "anagram", t = "nagaram"
• 輸出: True

s 重新排列之後可以變成跟 t 一樣的詞。

最佳解法

比較麻煩的地方是除了 character 要對之外，出現的次數以及兩字串的長度也都要相同，所以不適合用 set。

別懷疑，最簡單且最優 (雅?) 的解法就是直接 sort 下去。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

時間複雜度

O(nlogn)

冷知識

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

空間複雜度

O(1)

正常解法

這個方法分別 traverse s 跟 t 一次才能進行比對，時間複雜度跟空間複雜度都是 O(n)。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        hash_map1, hash_map2 = dict(), dict()

        for i in s:
            if i in hash_map1:
                hash_map1[i] += 1
            else:
                hash_map1[i] = 1

        for j in t:
            if j in hash_map2:
                hash_map2[j] += 1
            else:
                hash_map2[j] = 1

        return hash_map1 == hash_map2

或是一樣成為調 lib 超人…

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

• 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