LeetCode 242 Valid Anagram：字母頻率統計判斷異位詞

題目大意

給定兩字符串 s、t（僅含小寫字母），判斷 t 是否為 s 的異位詞（字母重新排列）。

O(n) 時間、O(1) 空間解法

• 長度不同直接 false。
• 建大小 26 的計數陣列 cnt，遍歷 s 做 ++，遍歷 t 做 --。
• 若過程中任一 cnt[i] < 0，說明 t 某字母過多，返回 false。
• 遍歷結束返回 true（長度相同且無負值 ⇒ 全為 0）。

參考代碼

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;
        int cnt[26] = {0};
        for (char c : s) ++cnt[c - 'a'];
        for (char c : t) if (--cnt[c - 'a'] < 0) return false;
        return true;
    }
};

複雜度與變體

• 時間 O(n)，空間 O(1)（固定 26 整數）。
• 若字符集擴大至 Unicode，改用 unordered_map，空間 O(k)（k 為不同字符數）。
• 排序法 O(n log n) 也可接受但非最優。

總結

異位詞判斷的核心是「字符多集合相等」。定長計數陣列利用字符集小的特性，實現最優線性時間、常數空間。面試中常作為哈希表/計數排序的入門考點。