242. Valid Anagram

Easy

Description

給定兩個字串 s 和 t，判斷 t 是否為 s 的 anagram（字母重新排列）。兩字串只包含小寫英文字母。

Example:

Input: s = “anagram”, t = “nagaram” Output: true

Intuition#

核心思路：Anagram 就是字母出現頻率完全相同——用計數陣列或排序後比較。

如果兩字串長度不同，直接回傳 false
Anagram 的本質：兩個字串的字元頻率分佈完全一致
只有 26 個小寫字母，可以用固定大小陣列計數

Approaches#

1: Sorting#

概念: 將兩個字串排序後直接比較，若相同則為 anagram
時間複雜度: O(n log n) - 排序主導
空間複雜度: O(n) - 排序需要額外空間（字串轉陣列）

class Solution {
    fun isAnagram(s: String, t: String): Boolean {
        if (s.length != t.length) return false
        val sArr = s.toCharArray().also { it.sort() }
        val tArr = t.toCharArray().also { it.sort() }
        return sArr.contentEquals(tArr)
    }
}

⭐2: Character Count Array#

概念: 用大小 26 的陣列計數，遍歷 s 時加一、遍歷 t 時減一，最終所有計數應為零
時間複雜度: O(n) - 各遍歷一次
空間複雜度: O(1) - 固定大小 26 的陣列

class Solution {
    fun isAnagram(s: String, t: String): Boolean {
        if (s.length != t.length) return false
        val count = IntArray(26)
        for (i in s.indices) {
            count[s[i] - 'a']++
            count[t[i] - 'a']--
        }
        return count.all { it == 0 }
    }
}

Follow-up：如果輸入包含 Unicode 字元，固定大小陣列不適用，需改用 HashMap<Char, Int> 來計數。

🔑 Takeaways#

Pattern: 字元頻率比較 -> 計數陣列（限定字元集）或 HashMap（通用）
關鍵技巧: 當字元集固定（如 26 個小寫字母），用陣列取代 HashMap 可以獲得更好的常數時間和空間效率