判斷短字符串字符是否全在長字符串中：從 O(nm) 到 O(n+m) 的演進

問題描述

給定長字符串 A 和短字符串 B，判斷 B 中每個字符是否都出現在 A 中。例：

• A=ABCDEFGHLMNOPQRS, B=DCGSRQPOM → true
• A=ABCDEFGHLMNOPQRS, B=DCGSRQPOZ → false (Z 不在 A 中)

方案演進

1. 暴力雙層循環 O(n×m)

對 B 中每字符掃描 A。n=16, m=9 時 144 次比較。代碼簡單但不可取。

2. 排序 + 雙指針掃描 O(n log n + m log m)

先對兩串排序，再雙指針線性掃描。隨長度增長優於暴力，但非最優。

// 快排 + 歸並式掃描
quicksort(A); quicksort(B);
i=j=0;
while (i<lenA && j<lenB) {
    if (A[i] < B[j]) i++;
    else if (A[i] == B[j]) { i++; j++; }
    else break; // B[j] 不在 A 中
}
return j == lenB;

3. 位圖/哈希表 O(n + m) —— 最優解

利用字符集有限（ASCII 256 或字母 52）建立查找表：

• 掃描 A，在 `bool seen[256]={0}` 標記出現字符
• 掃描 B，檢查 `seen[B[i]]` 是否全為真

時間 O(n+m)，空間 O(1)（固定 256 字節）。

C++ 實現（位圖版）

bool containsAll(const string &A, const string &B) {
    bool seen[256] = {false};
    for (char c : A) seen[(unsigned char)c] = true;
    for (char c : B) if (!seen[(unsigned char)c]) return false;
    return true;
}

進階：字母-only 時的 64 位整數位掩碼

若僅含 a-z，一個 uint64_t 即可：

uint64_t mask = 0;
for (char c : A) mask |= 1ULL << (c - 'a');
for (char c : B) if (!(mask & (1ULL << (c - 'a')))) return false;
return true;

單指令位運算，極致高效。

面試官進階追問

1. Unicode 怎麼辦？ → 用 `unordered_set` 或排序+二分
2. 需統計出現次數？ → 用 `int count[256]` 計數
3. 極長字符串（GB 級）？ → 流式處理 + 位圖，內存不變

總結

本題核心在於識別「字符集有限」這一關鍵特性，從而將查找從 O(n) 降為 O(1)。位圖/哈希表是工程中處理「集合包含關係」的通用利器。