C# 判斷兩等長字串是否包含完全相同字符（忽略順序）的高效演算法

問題定義

給定兩等長字串，判斷其是否由完全相同的字符組成（順序無關、重複次數必須一致）。例："北京歡迎你" vs "歡迎你北京" → True；"4455" vs "4555" → False。

演算法演進

版本 1：雙重 Contains（錯誤）

foreach (char c in strA) if (!strB.Contains(c)) return false;
foreach (char c in strB) if (!strA.Contains(c)) return false;
return true;

缺陷：無法檢測字符出現次數差異（如 "4455" vs "4555" 會誤判為 True）。

版本 2：逐字符計數比對（正確但 O(n²)）

foreach (char c in arrA) {
    if (!strB.Contains(c)) return false;
    if (Count(c, arrA) != Count(c, arrB)) return false;
}
// 對 arrB 同理

雙重迴圈計數，效率隨長度增長急劇下降。

版本 3：List 同步移除法（O(n²) 但常數較小）

var listA = strA.ToList();
var listB = strB.ToList();

for (int i = 0; i < listA.Count; i++) {
    for (int j = 0; j < listB.Count; j++) {
        if (listA[i] == listB[j]) {
            listA.RemoveAt(i);
            listB.RemoveAt(j);
            i--; j--;
            break;
        }
    }
}
return listA.Count == 0 && listB.Count == 0;

利用配對消除思想，直觀易懂，但 RemoveAt 導致陣列位移，仍屬 O(n²)。

最佳解法：字符頻率統計（O(n)）

public static bool AreAnagrams(string a, string b) {
    if (a.Length != b.Length) return false;
    int[] freq = new int[65536]; // Unicode BMP 範圍
    foreach (char c in a) freq[c]++;
    foreach (char c in b) {
        if (--freq[c] < 0) return false;
    }
    return true;
}

• 時間複雜度 O(n)，空間 O(1)（固定 65536 int）。
• 適用於任意 Unicode 字符（含中文、表情符號）。
• 若確定僅 ASCII，可縮減為 int[128] 或 int[256]。

進階：LINQ 一行寫法（教學用）

return a.Length == b.Length && 
       a.GroupBy(c => c).Select(g => new { Char = g.Key, Count = g.Count() })
        .SequenceEqual(b.GroupBy(c => c).Select(g => new { Char = g.Key, Count = g.Count() }));

可讀性佳但分配大量物件，不適合高頻呼叫。

總結

生產環境請直接使用頻率陣列法，兼具效能與正確性。