---
title: "242. Valid Anagram"
url: "https://laigary.com/interview/coding/242-valid-anagram"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-08-02"
tags: ["Hash Table"]
---

# 242. Valid Anagram

[242. Valid Anagram](https://leetcode.com/problems/valid-anagram/)

給兩個字串 `s` 和 `t`，問 `t` 是不是 `s` 的 anagram —— 也就是用完全一樣的字元、只是順序不同。

## 思路

Anagram 有一個特性就是只要是 Anagram 每個字元的字數都會一樣多，因此一個解法是先計算出一個單字每個字元所出現的次數，接著是再減去另外一個單字，有出現的字元的字數。

如果中間有發現其他的字元，就代表不是 Anagram 。

最後還要再記得檢查，有沒有哪個字元有在第一個單字有出現，但是第二個單字沒有出現。

所以是三個步驟：**數 `s` → 用 `t` 去扣 → 看有沒有剩**。三個迴圈剛好對應這三件事。

## 解題方向

```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        table = defaultdict(int)
        for char in s:
            table[char] += 1

        for char in t:
            if table[char] > 0:
                table[char] -= 1
            else:
                return False

        for key in table.keys():
            if table[key] != 0:
                return False

        return True

```

## 補充

### 第三個迴圈可以用一行長度檢查取代

第三個迴圈是在處理「`s` 比 `t` 長」的情況：`s = "aab"`、`t = "ab"` 時，前兩個迴圈都會過關，是最後這個迴圈抓到 `a` 還剩 1。

換句話說，只要先擋掉長度不同的情況，它就沒事可做了：

```python
if len(s) != len(t):
    return False
```

因為長度一樣、而且扣的過程中沒有任何一個字元扣到負的，那總共扣掉的次數就等於總共加上去的次數，每個計數最後一定都是 0。

兩個版本我都跑過 20000 組隨機字串對 `sorted(s) == sorted(t)`，都是全對。但**只拿掉第三個迴圈、又不加長度檢查**就會壞 —— `"aab"` 和 `"ab"` 會回傳 `True`。

### `table[char]` 會順手把 key 建出來

`defaultdict` 的讀取不是單純的讀 —— 讀到不存在的 key 時，它會**當場把那個 key 用預設值建進字典**：

```python
table = defaultdict(int)
for c in "abc":
    table[c] += 1
# {'a': 1, 'b': 1, 'c': 1}

_ = table['z'] > 0
# {'a': 1, 'b': 1, 'c': 1, 'z': 0}   <- 只是讀了一下，'z' 就進來了
```

在這題無害（第二個迴圈跑的是 `t` 不是字典，多出來的 key 值都是 0，第三個迴圈也不會誤判）。但要知道兩件事：**一是字典會比預期大**，二是**如果哪天在迴圈裡邊迭代同一個字典邊這樣讀，就會 `RuntimeError: dictionary changed size during iteration`**。不想有這個副作用就用 `table.get(char, 0)`。

### Unicode 的 follow-up

題目最後問「如果輸入是 Unicode 字元呢」。用字典計數的寫法**本來就已經過關了** —— 會需要改的是那種開一個長度 26 的陣列、用 `ord(c) - ord('a')` 當索引的版本。

## 複雜度

設 $n$、$m$ 是兩個字串的長度，$k$ 是出現過的相異字元數。

- 時間 $O(n + m)$ — 兩個字串各掃一次；最後掃字典是 $O(k)$，而 $k \le n$，所以不影響
- 空間 $O(k)$ — 字典裡的相異字元數。如果限定小寫英文字母，$k \le 26$，可以說是 $O(1)$