題目描述

給定兩個字符串 s 和 t，編寫函數判斷 t 是否為 s 的字母異位詞。

示例：

• s = "anagram", t = "nagaram" → 返回 true
• s = "rat", t = "car" → 返回 false

說明： 假設字符串僅包含小寫字母。

進階： 若輸入包含 Unicode 字符，如何調整解法？

解題思路

核心思路：先排序，再比較是否相等。若兩字符串排序後完全一致，則互為字母異位詞。

代碼實現

Java 版本

// Runtime: 8 ms
public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        Arrays.sort(s1);
        Arrays.sort(t1);
        return String.valueOf(s1).equals(String.valueOf(t1));
    }
}

替代方案：字符計數法（O(n) 時間複雜度）

利用長度為 26 的整型數組統計每個小寫字母出現次數，遍歷 s 計數器加 1，遍歷 t 計數器減 1，最後檢查所有計數是否為 0。此法可自然擴展至 Unicode 字符（使用 HashMap）。

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int c : count) {
            if (c != 0) return false;
        }
        return true;
    }
}

複雜度分析

• 排序法：時間 O(n log n)，空間 O(1)（不計輸入空間）
• 計數法：時間 O(n)，空間 O(1) / O(k)（k 為字符集大小）