給定兩個字串
s和t，判斷t是否為s的 anagram（字母重新排列）。兩字串只包含小寫英文字母。
Example:
Input: s = “anagram”, t = “nagaram” Output: true
Intuition
TIP
核心思路：Anagram 就是字母出現頻率完全相同——用計數陣列或排序後比較。
- 如果兩字串長度不同，直接回傳
false - Anagram 的本質：兩個字串的字元頻率分佈完全一致
- 只有 26 個小寫字母，可以用固定大小陣列計數
Approaches
1. Sorting — O(n log n) / O(n)
- Idea: 將兩個字串排序後直接比較，若相同則為 anagram
- Time:
O(n log n)- 排序主導 - Space:
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 — O(n) / O(1)
- Idea: 用大小 26 的陣列計數，遍歷
s時加一、遍歷t時減一，最終所有計數應為零 - Time:
O(n)- 各遍歷一次 - Space:
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 }
}
}WARNING
Follow-up：如果輸入包含 Unicode 字元，固定大小陣列不適用，需改用 HashMap<Char, Int> 來計數。
🔑 Takeaways
- Pattern: 字元頻率比較 -> 計數陣列（限定字元集）或 HashMap（通用）
- Key trick: 當字元集固定（如 26 個小寫字母），用陣列取代 HashMap 可以獲得更好的常數時間和空間效率