題目資訊

• 題目編號: 242
• 題目連結: Valid Anagram
• 主題: Hash Table, String, Sorting

題目敘述

給定兩個字串 s 和 t，如果 t 是 s 的異位詞，則返回 true，否則返回 false。

範例 1:

輸入: s = “anagram”, t = “nagaram”

輸出: true

範例 2:

輸入: s = “rat”, t = “car”

輸出: false

限制條件:

• $1 \leq s.length, t.length \leq 5 \times 10^4$
• s 和 t 由小寫英文字母組成。

後續問題: 如果輸入包含 Unicode 字元，該如何調整你的解決方案以應對這種情況？

直覺

異構詞是一種透過重新排列另一個單字或片語中的字母組合而成的單字或片語，通常是每個原始字母僅使用一次。這個問題要求判斷一個字串是否為另一個字串的異構詞。主要的觀察點是，如果兩個字串滿足條件，即它們各自的字母出現頻率是一致的，那麼它們就是異構詞。由於字串由小寫英文字母組成，我們可以使用一個數組來有效地計數這些字母的頻率。

解法

為了解決這個問題，我們使用一個固定大小為26的數組來考慮每個小寫英文字母。數組初始化時所有元素為零，對應於字母從 ‘a’ 到 ‘z’。演算法主要有以下幾個步驟：

1. 第一個字串的頻率計數：

   • 遍歷字串 s，並對每個字元在 letter_count 數組中的對應索引進行遞增。具體而言，對於字串 s 中的某個字元 ch，更新數組中索引為 ch - 'a' 的位置以反映增加後的計數。

2. 調整第二個字串的頻率計數：

   • 遍歷字串 t，並對每個字元在 letter_count 數組中的對應索引進行遞減。同樣地，對於字串 t 中的某個字元 ch，更新數組中索引為 ch - 'a' 的位置以反映減少後的計數。

3. 異構詞狀態的確認：

   • 處理完兩個字串後，檢查 letter_count 數組。如果所有計數均為零，則這意味著兩個字串的字符頻率相同，確認 t 是 s 的異構詞。如果有任何計數不為零，這表示字母頻率有差異，意味著 t 不是 s 的異構詞。

透過這種技術，我們可以有效地判斷兩個字串是否為異構詞，具體地說就是比較字元頻率映射。此方法的複雜度是線性的，即 $O(n)$，其中 $n$ 是字串的長度（假設兩個字串的長度相同），使其非常適合解決此問題的限制條件。

程式碼

C++

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 一個陣列用來記錄英文字母的頻率
        int letter_count[26] = {0};

        // 遍歷第一個字串並增加每個字母的計數
        for (char ch : s) {
            letter_count[ch - 'a']++;
        }

        // 遍歷第二個字串並減少每個字母的計數
        for (char ch : t) {
            letter_count[ch - 'a']--;
        }

        // 檢查所有計數是否都為零，這意味着它們是異位詞
        for (int count : letter_count) {
            if (count != 0) {
                return false; // 如果任何計數不為零，則不是異位詞
            }
        }
        
        return true; // 如果所有計數都為零，表示 t 是 s 的異位詞
    }
};

Python

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # 使用陣列來計算英文字母中每個字母的頻率
        letter_count = [0] * 26

        # 對於第一個字串中的每個字元，增加其計數
        for ch in s:
            letter_count[ord(ch) - ord('a')] += 1

        # 對於第二個字串中的每個字元，減少其計數
        for ch in t:
            letter_count[ord(ch) - ord('a')] -= 1

        # 檢查所有計數是否為零，這表示它們是異位詞
        for count in letter_count:
            if count != 0:
                return False  # 若任何計數不為零，則不是異位詞
        
        return True  # 若所有計數都為零，表示 t 是 s 的異位詞

複雜度分析

• 時間複雜度: 該演算法的時間複雜度是 $O(n + m)$，其中 $n$ 是字串 $s$ 的長度，$m$ 是字串 $t$ 的長度。這是因為演算法需要遍歷這兩個字串的每個字符各一次，以在 letter_count 陣列中計算和調整頻率。
• 空間複雜度: 空間複雜度是 $O(1)$，因為該演算法使用一個固定大小的陣列來儲存英文字母頻率。此空間不會隨輸入大小擴展，僅依賴於字母表的固定大小。