C 語言字串刪除指定字符：高效 O(n) 原地算法實現

在字串 A 中刪除所有出現在字串 B 中的字符，是經典的字串處理面試題。本文提供O(n + m) 時間、O(1) 空間的原地刪除算法，附完整代碼與關鍵技巧解析。

問題定義

• 輸入：字串 A (可修改)、字串 B (刪除字符集)
• 輸出：修改後的 A，移除所有 B 中出現的字符
• 範例：A = "hello world", B = "ewd" → A = "hllo orl"

核心算法：查找表 + 雙指針原地覆蓋

void deleteWord(char *dest, char *word) {
    int len1 = strlen(dest);
    int len2 = strlen(word);

    // 1. 建立字符查找表 (ASCII 256)
    int lookup[256] = {0};
    for (int i = 0; i < len2; i++)
        lookup[(unsigned char)word[i]] = 1;  // 標記需刪除字符

    // 2. 雙指針原地覆蓋
    int write_idx = 0;
    for (int read_idx = 0; read_idx < len1; read_idx++) {
        if (!lookup[(unsigned char)dest[read_idx]]) {
            dest[write_idx++] = dest[read_idx];  // 保留字符前移
        }
    }
    dest[write_idx] = '\0';  // 新字串結束
}

關鍵技巧解析

完整可運行程式

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void deleteWord(char *dest, char *word) {
    int len1 = strlen(dest);
    int len2 = strlen(word);
    int lookup[256] = {0};
    for (int i = 0; i < len2; i++)
        lookup[(unsigned char)word[i]] = 1;
    int write_idx = 0;
    for (int read_idx = 0; read_idx < len1; read_idx++) {
        if (!lookup[(unsigned char)dest[read_idx]])
            dest[write_idx++] = dest[read_idx];
    }
    dest[write_idx] = '\0';
}

int main() {
    char a[] = "hello world";
    char b[] = "ewd";
    printf("Input A: %s\n", a);
    printf("Input B: %s\n", b);
    deleteWord(a, b);
    printf("After delete: %s\n", a);  // 輸出: hllo orl
    return 0;
}

原文代碼問題分析

原文使用後移法：刪除字符時將後續所有字符向前移一位：

// 原文做法：刪除時後移
if (lookup[dest[j]]) {
    for (int i = j; i < len1 - 1; i++)
        dest[i] = dest[i+1];
    dest[len1-1] = '\0';
    j--; len1--;  // 補償索引與長度
}

缺點：最壞情況 (全刪除) 時間複雜度 O(n²)，每次刪除移動 O(n) 字符。雙指針法嚴格 O(n)，且代碼更簡潔。

擴展場景

• Unicode/多位元組字符：需改用哈希表或 Trie 存儲刪除集，按字符而非位元組處理
• 大小寫不敏感：建表時統一轉大寫/小寫，查詢時同樣轉換
• 刪除子串而非單字符：需 KMP/BM 算法定位子串，再用雙指針覆蓋
• C++ string 版本：

  void deleteChars(string &s, const string &chars) {
      bool lookup[256] = {false};
      for (unsigned char c : chars) lookup[c] = true;
      size_t w = 0;
      for (size_t r = 0; r < s.size(); r++)
          if (!lookup[(unsigned char)s[r]]) s[w++] = s[r];
      s.resize(w);
  }

複雜度總結

掌握查找表 + 雙指針原地覆蓋模式，可解決「過濾/刪除/保留字符」大類問題，是字串處理的核心套路。