242. Valid Anagram

題目 / Problem

中文： 給定兩個字串 s 和 t，如果 t 是 s 的字母異位詞（anagram），回傳 true，否則回傳 false。所謂字母異位詞，是指由完全相同的字母、以完全相同的數量、但可能不同順序排列而成的字串。

English: Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram uses exactly the same letters with exactly the same counts, just possibly in a different order.

Constraints / 限制條件: - 1 <= s.length, t.length <= 5 * 10^4 - s 和 t 只包含小寫英文字母 / s and t consist of lowercase English letters.

Worked example / 範例: - Input: s = "anagram", t = "nagaram" → Output: true（兩者都由 3 個 a、1 個 n、1 個 g、1 個 r、1 個 m 組成） - Input: s = "rat", t = "car" → Output: false（s 有 t 但沒有 c）

名詞解釋 / Glossary

• 字母異位詞 / anagram：兩個字串包含完全相同的字母種類與數量，只是排列順序可能不同。例如 "listen" 和 "silent"。/ Two strings made of the exact same letters in the exact same counts, just reordered.
• 雜湊表 / hash map：一種把「鍵 (key)」對應到「值 (value)」的資料結構，查詢與更新平均都是 O(1)。這裡我們用它來記錄每個字母出現幾次。/ A data structure mapping keys to values with average O(1) lookup; here it counts how many times each letter appears.
• 計數陣列 / frequency array：當鍵的範圍很小（例如 26 個小寫字母）時，可以直接用一個固定大小的陣列代替雜湊表，索引就是字母、值就是次數。比雜湊表更快更省。/ When keys are few (e.g. 26 lowercase letters), a fixed-size array replaces the hash map: the index is the letter, the value is its count.
• ASCII 值 / ASCII value：每個字元在電腦裡其實是一個整數編碼。小寫 'a' 是 97、'b' 是 98……所以 c - 'a' 會得到 0~25 的索引。/ Each character is stored as an integer code; 'a' is 97, so c - 'a' gives an index 0–25.
• 時間複雜度 / time complexity：用來描述演算法執行時間如何隨輸入大小成長的記號，例如 O(n) 表示「與 n 成正比」。/ Notation describing how runtime grows with input size; O(n) means proportional to n.

思路

中文：最直覺的暴力解法是把兩個字串都「排序」，如果排序後完全一樣，那它們就是字母異位詞。這個方法正確，但排序需要 O(n log n) 的時間，比必要的慢。更好的觀察是：字母異位詞的本質就是「每個字母出現的次數都一樣」。所以我們不需要在乎順序，只要數一數每個字母出現幾次就好。由於題目保證只有 26 個小寫字母，我們可以開一個大小為 26 的計數陣列 count，索引 c - 'a' 對應字母 c。第一步：先檢查兩字串長度，如果長度不同，絕對不可能是異位詞，直接回傳 false（這也是一個很有用的提早剪枝）。第二步：掃過 s，把每個字母的計數 +1；同時掃過 t，把每個字母的計數 -1。如果 s 和 t 的字母組成完全相同，那麼每個字母被加的次數會剛好等於被減的次數，最後整個 count 陣列會全部歸零。第三步：檢查 count 是否全為 0，只要有任何一格不是 0，就代表某個字母在兩邊數量不一致，回傳 false。這個方法只掃過字串常數次，時間是 O(n)，而陣列固定 26 格，額外空間是 O(1)。

English: The most obvious brute force is to sort both strings and compare — if the sorted versions are identical, they're anagrams. That works but sorting costs O(n log n), more than we need. The key insight is that being an anagram means every letter appears the same number of times in both strings; order is irrelevant. So instead of sorting, we just count letters. Because the input is limited to 26 lowercase letters, we use a fixed count array of size 26, where index c - 'a' represents letter c. Step one: if the two lengths differ, they can't be anagrams — return false immediately (a cheap, useful early exit). Step two: walk through s adding 1 to each letter's count, and walk through t subtracting 1. If the letter compositions match exactly, every increment is cancelled by a matching decrement, so the whole array ends at zero. Step three: scan the array; if any slot is non-zero, some letter's counts didn't match, so return false. We only pass over the strings a constant number of times — O(n) time — and the array is a fixed 26 slots, so O(1) extra space.

逐步走查 / Walkthrough

以 s = "anagram", t = "nagaram" 為例 / Using s = "anagram", t = "nagaram":

長度檢查 / Length check：s 長度 7，t 長度 7，相等，繼續 / equal, continue.

掃描 s（每個字母 count[c-'a'] += 1）/ Scan s (increment):

掃描 t（每個字母 count[c-'a'] -= 1）/ Scan t (decrement):

最終檢查 / Final check：所有 26 格都是 0 → 回傳 true / all slots are 0 → return true. ✅

Solution — C

// 演算法 / Algorithm:
// 用大小 26 的計數陣列，掃 s 時每個字母 +1，掃 t 時 -1；
// 若兩字串是異位詞，計數最終全部歸零。長度不同則直接 false。
// Use a size-26 count array: +1 for each letter of s, -1 for each of t.
// If they're anagrams every count returns to 0. Different lengths => false.

#include <string.h>   // 為了 strlen / for strlen
#include <stdbool.h>  // 為了 bool / true / false 型別 / for the bool type

bool isAnagram(char* s, char* t) {
    // strlen 回傳字串長度（不含結尾的 ''）/ strlen returns string length (excluding the '').
    int lenS = strlen(s);
    int lenT = strlen(t);

    // 長度不同必不可能是異位詞，提早結束省時間 / Different lengths can't be anagrams — early exit.
    if (lenS != lenT) return false;

    // 26 格計數陣列，全部初始化為 0；索引 0..25 對應字母 a..z
    // A 26-slot count array initialized to 0; indices 0..25 map to letters a..z.
    int count[26] = {0};

    // 掃過 s 的每個字元，對應計數 +1
    // Walk every char of s, incrementing its count.
    for (int i = 0; i < lenS; i++) {
        // s[i] 是一個字元；s[i] - 'a' 把字母轉成 0..25 的索引
        // s[i] is a char; s[i] - 'a' converts the letter to an index 0..25.
        count[s[i] - 'a']++;
    }

    // 掃過 t 的每個字元，對應計數 -1
    // Walk every char of t, decrementing its count.
    for (int i = 0; i < lenT; i++) {
        count[t[i] - 'a']--;
    }

    // 檢查是否所有計數都歸零；只要有一格非 0 就不是異位詞
    // Check all counts are zero; any non-zero slot means not an anagram.
    for (int i = 0; i < 26; i++) {
        if (count[i] != 0) return false;
    }

    // 全部歸零，s 和 t 字母組成完全相同 / All zero: identical letter composition.
    return true;
}

Solution — C++

// 演算法 / Algorithm:
// 同樣用大小 26 的計數陣列，s 的字母 +1、t 的字母 -1，
// 最後若全為 0 即為異位詞。長度不同直接回傳 false。
// Same size-26 count array: +1 for s's letters, -1 for t's letters.
// All zeros at the end means anagram; different lengths => false.

#include <string>
#include <array>   // 為了 std::array 固定大小陣列 / for std::array, a fixed-size array
using namespace std;

class Solution {
public:
    bool isAnagram(string s, string t) {
        // string 的 .size() 回傳字元數 / .size() returns the number of characters.
        // 長度不同必不可能是異位詞 / Different lengths can't be anagrams.
        if (s.size() != t.size()) return false;

        // std::array<int,26> 是固定 26 格的陣列，{} 讓所有元素初始化為 0
        // std::array<int,26> is a fixed 26-element array; {} zero-initializes all of them.
        array<int, 26> count{};

        // range-for：依序取出 s 的每個字元 c（無需手動管理索引）
        // Range-for: iterate each character c of s without manual indexing.
        for (char c : s) {
            // c - 'a' 把字母轉成 0..25 的索引，對應計數 +1
            // c - 'a' maps the letter to index 0..25; increment that count.
            count[c - 'a']++;
        }

        // 對 t 的每個字元，對應計數 -1
        // For each character of t, decrement the matching count.
        for (char c : t) {
            count[c - 'a']--;
        }

        // 檢查是否所有計數都為 0；任一非 0 表示字母數量不一致
        // Verify every count is 0; any non-zero means letter counts differ.
        for (int v : count) {
            if (v != 0) return false;
        }

        // 全部歸零 → 是異位詞 / All zero -> it's an anagram.
        return true;
    }
};

複雜度 / Complexity

• Time: O(n) — 我們對 s 掃一次、對 t 掃一次、再對固定 26 格的計數陣列掃一次。前兩個與字串長度 n 成正比，最後一個是常數 26，所以整體由 O(n) 主導。/ We scan s once, t once, and the fixed 26-slot array once. The first two scale with the string length n; the last is a constant 26, so O(n) dominates. Here n is the string length.
• Space: O(1) — 不論輸入多長，計數陣列永遠只有 26 格，是固定的常數空間，不隨 n 成長。/ Regardless of input size, the count array is always 26 slots — fixed, constant space that does not grow with n.

Pitfalls & Edge Cases

• 長度不同 / Different lengths：若先不檢查長度，像 s = "a", t = "ab" 這種情況可能漏判。先比長度既正確又能提早結束。/ Without the length check, cases like "a" vs "ab" can slip through. Comparing lengths first is both correct and a fast early exit.
• 只用一個陣列就夠 / One array suffices：用「+1 再 -1」的技巧，不需要開兩個陣列再逐格比較，省一半空間，也更不易寫錯。/ The +1/−1 trick avoids needing two arrays and a separate comparison loop — half the space and fewer bugs.
• 索引一定要 c - 'a' / Always offset by 'a'：直接用 count[c] 會越界，因為 'a' 的 ASCII 是 97，陣列只有 26 格。必須減掉 'a' 才能落在 0~25。/ Using count[c] directly overflows since 'a' is 97 and the array is only 26 long; subtract 'a' to land in 0–25.
• 假設只有小寫字母 / Assumes lowercase only：本解法依賴「只有 26 個小寫字母」的限制。若出現大寫或其他字元會算錯或越界。/ This relies on the lowercase-only constraint; uppercase or other characters would miscount or go out of bounds.
• Follow-up（Unicode）：若輸入可能是 Unicode（成千上萬種字元），固定 26 格不夠用。改用雜湊表 unordered_map<char32_t,int>（或 C 裡的雜湊結構）依實際出現的字元動態計數即可。/ For Unicode input, a fixed 26 slots won't work; switch to a hash map keyed by the actual characters seen and count dynamically.
• 空字串不會發生 / No empty strings：限制保證長度 ≥ 1，但即使是空字串，本演算法仍會正確回傳 true（兩個空字串互為異位詞）。/ Constraints guarantee length ≥ 1, but the algorithm would still correctly return true for two empty strings anyway.