PAT 1050 String Subtraction：字符集過濾 O(n) 解法

題目

給定字符串 S1、S2，輸出 S1 - S2：即刪除 S1 中所有出現在 S2 的字符。長度 ≤ 10⁴，可見 ASCII + 空白。

解法：查找表過濾

1. 建立大小 256 的布爾數組 bad[ch]，標記 S2 中出現的字符。
2. 遍歷 S1，若 !bad[ch] 則輸出。

C++ AC 代碼

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    bool bad[256] = {false};
    for (char c : s2) bad[(unsigned char)c] = true;
    for (char c : s1) if (!bad[(unsigned char)c]) cout << c;
    return 0;
}

複雜度

• 時間：O(|S1| + |S2|)。
• 空間：O(1)（固定 256 字節）。

注意點

• 輸入可能含空格，必須用 getline。
• char 有符號性實現定義，下標轉 unsigned char 避免負索引。