題目網址：https://leetcode.cn/problems/valid-anagram/

題意：給兩 string s 和 t, 返回 t 是否為 s 的字母異位詞(Anagram) 則返回 true, 其中 s 和 t 僅由小寫字母所組成。

字母異位詞 (Anagram) 定義：若 s 和 t 中每個字母的出現次數都相同, 則 s 和 t 互為字母異位詞。

進階：若 input string 包含 Unicode char, 你要如何調整你的解法？

Solution 1：

想法：將 s、t 進行排序, 若排序後 s、t 相等, 就代表為 anagram

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }

        sort(s.begin(), s.end());
        sort(t.begin(), t.end());

        return s == t;
    }
};
  • time：$O(n \cdot log(n))$ ➔ sorting
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：利用 Array 來記錄每個字母的出現次數, 若 s 和 t 為 anagram, 則 s 中每個字母的出現頻率 - t 中每個字母的出現頻率 後, 每個字母的出現頻率應皆為 0

e.g. s = "abc", t = "cba"

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }

        vector<int> freqs(26, 0);
        for (const auto& ch : s) {
            ++freqs[ch - 'a'];
        }

        // 在 s 和 t 長度相等的情況下, 若不為 anagram, 則必存在一 char 相減後的 freq < 0
        for (const auto& ch : t) {
            if (--freqs[ch - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};
  • time：$O(n)$ ➔ 遍歷 s 和 t
  • space：$O(1)$ ➔ $O(26)$, 只需常數空間

Solution 3：

想法：利用 hash table, 概念同 Solution 1, 但是 Solution 1 只能解決 s 和 t 為小寫字母的問題, Solution 2 可解決 input string 包含 Unicode char 的問題

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }

        unordered_map<char, int> freqs;
        for (const auto& ch : s) {
            ++freqs[ch];
        }

        for (const auto& ch : t) {
            if (--freqs[ch] < 0) {
                return false;
            }
        }

        return true;
    }
};
  • time：$O(n)$ ➔ 遍歷 s 和 t
  • space：$O(S)$ ➔ $S$ 為 s 和 t union 後的 char set 之元素個數, 本題的 S = 26