LeetCode 242：有效字母異位詞

題目：給定兩字符串 s、t，判斷 t 是否為 s 的字母異位詞（字符種類與次數完全相同）。

三種解法

1. 排序法：將兩字符串轉字符數組排序，比較是否相等。時間 O(n log n)，空間 O(1)（或 O(n) 視排序實現）。
2. 哈希表法：用 Map<Character, Integer> 統計 s 中字符頻次，遍歷 t 遞減計數，若缺鍵或計數歸零則 false。時間 O(n)，空間 O(k)（k 為字符集大小）。
3. 定長數組法（最優）：ASCII 字符集 256 足夠，用 int[256] 計數。遍歷 s 加計數，遍歷 t 減計數，若任一計數變負則 false。時間 O(n)，空間 O(1)（固定 256）。

Java 實現（三合一）

public class ValidAnagram {
    // 排序法
    public static boolean isAnagram(String s, String t) {
        if (s == null || t == null) return false;
        if (s.length() != t.length()) return false;
        char[] a = s.toCharArray(), b = t.toCharArray();
        Arrays.sort(a); Arrays.sort(b);
        return Arrays.equals(a, b);
    }

    // 哈希表法
    public static boolean isAnagram2(String s, String t) {
        if (s == null || t == null) return false;
        if (s.length() != t.length()) return false;
        Map map = new HashMap<>();
        for (char c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);
        for (char c : t.toCharArray()) {
            if (!map.containsKey(c)) return false;
            if (map.get(c) <= 0) return false;
            map.put(c, map.get(c) - 1);
        }
        return true;
    }

    // 定長數組法
    public static boolean isAnagram3(String s, String t) {
        if (s == null || t == null) return false;
        if (s.length() != t.length()) return false;
        int[] cnt = new int[256];
        for (char c : s.toCharArray()) cnt[c]++;
        for (char c : t.toCharArray()) if (--cnt[c] < 0) return false;
        return true;
    }
}

小結

字母異位詞本質是多重集合相等。定長數組法利用字符集有限特性，時空效率最優，面試首選。