判斷兩字符串是否為變位詞：字符計數法 O(n)

題目

給定兩字符串 s1、s2，判斷是否互為變位詞（Anagram）：字符種類與次數完全相同，順序可不同。例如 abbfcad 與 facbdab。

核心思想：字符頻率統計

不需排序（O(n log n)），利用定長數組計數：

1. 長度不同 → 直接 false。
2. 開啟 int cnt[26] = {0}（假設小寫字母）。
3. 遍歷 s1，cnt[ch-'a']++。
4. 遍歷 s2，cnt[ch-'a']--。
5. 檢查 cnt 全為 0 → true，否則 false。

C++ 實現

#include 
#include 
using namespace std;

bool isAnagram(const string& s1, const string& s2) {
    if (s1.length() != s2.length()) return false;
    int cnt[26] = {0};
    for (char c : s1) ++cnt[c - 'a'];
    for (char c : s2) if (--cnt[c - 'a'] < 0) return false; // 提前剪枝
    return true;
}

int main() {
    string a = "abbfcad", b = "facbdab", c = "facbkab";
    cout << a << " & " << b << " -> " << (isAnagram(a,b)?"Anagram":"Not") << endl;
    cout << a << " & " << c << " -> " << (isAnagram(a,c)?"Anagram":"Not") << endl;
    return 0;
}

輸出

abbfcad & facbdab -> Anagram
abbfcad & facbkab -> Not

複雜度

• 時間：O(n)，單次遍歷。
• 空間：O(1)，固定 26 整數（擴展到 ASCII 256 或 Unicode 需哈希表）。

擴展：任意字符集

bool isAnagramUnicode(const string& s1, const string& s2) {
    if (s1.size() != s2.size()) return false;
    unordered_map cnt;
    for (char c : s1) ++cnt[c];
    for (char c : s2) if (--cnt[c] < 0) return false;
    return true;
}

總結

「排序比較」雖直觀但非最優。「計數法」利用有限字符集特性，將時間降至線性，是面試中判斷變位詞的標準答案。同樣思想適用於「字符統計」、「找出唯一字符」等問題。