【算法】 【c++】字符串s1 中刪除所有 s2 中出現的字符
eg：
s1:“helloworld”
s2:“wd”
刪除后：s1:“helloorl”
1 雙循環匹配并刪除–>時間復雜度O(n^2)
string 里面的刪除函數–>erase
std::string::erase` 是 C++ 標準庫中用于刪除字符串中字符或子串的方法。
1. erase(pos, len)
- 作用：從字符串的 索引
pos位置開始，刪除len個字符。 - 參數：
- pos：起始索引（從
0開始）。 - len：要刪除的字符數量（默認值
std::string::npos，即刪除到末尾）。
- pos：起始索引（從
- 返回值：修改后的 string 自身（
左移剩余字符）。
示例
#include <iostream>
#include <string>using namespace std;int main() {string s = "abcdef";s.erase(2, 2); // 從索引 2 ('c') 開始刪除 2 個字符，變成 "abef"cout << s << endl; // 輸出: "abef"return 0;
}
2. erase(iterator pos)
- 作用：刪除
pos迭代器指向的字符。 - 參數：
pos：指向要刪除字符的 迭代器。
- 返回值：指向刪除字符后 下一個字符的迭代器。
示例
#include <iostream>
#include <string>using namespace std;int main() {string s = "abcdef";auto it = s.begin() + 2; // 指向 'c's.erase(it); // 刪除 'c'，變成 "abdef"cout << s << endl; // 輸出: "abdef"return 0;
}
3. erase(iterator first, iterator last)
- 作用：刪除
[first, last)范圍內的字符（包括first，不包括last）。 - 參數：
first：起始迭代器。last：結束迭代器（不刪除）。
- 返回值：指向刪除區域后第一個剩余字符的迭代器。
示例
#include <iostream>
#include <string>using namespace std;int main() {string s = "abcdef";s.erase(s.begin() + 1, s.begin() + 4); // 刪除索引 1~3 ('b' 到 'd')，變成 "aef"cout << s << endl; // 輸出: "aef"return 0;
}
4. erase-remove慣用法（高效刪除多個字符）
在 C++ 里，erase 不能直接刪除多個 指定字符，但可以配合 std::remove_if 實現 高效批量刪除：
示例
#include <iostream>
#include <string>
#include <algorithm>using namespace std;int main() {string s = "abcdebc";// 刪除所有 'b's.erase(remove(s.begin(), s.end(), 'b'), s.end());cout << s << endl; // 輸出: "acdec"return 0;
}
原理：
remove把所有 非 ‘b’ 的字符 重新排列到前面，返回新末尾的迭代器。erase刪除新末尾之后的所有字符，完成去重。
總結
| 用法 | 作用 | 適用場景 |
|---|---|---|
erase(pos, len) | 從 pos 開始刪除 len 個字符 | 刪除固定范圍的子串 |
erase(iterator pos) | 刪除 pos 迭代器指向的字符 | 通過迭代器刪除單個字符 |
erase(iterator first, iterator last) | 刪除 [first, last) 范圍字符 | 通過迭代器刪除一段子串 |
erase(remove_if(...)) | 批量刪除多個指定字符 | 需要高效刪除多個字符 |
#include<iostream>
using namespace std;
#include<string>
#include<vector>
void dele(string& s1, string& s2)
{int n2 = s2.size();if (n2 < 1)return;for (int i = 0;i < s1.size();i++){for (int j = 0;j < n2;j++){if (s1[i] == s2[j]){s1.erase(i,1);i--;}}}}
int main()
{string s1, s2;cin >> s1 >> s2;dele(s1, s2);cout << s1 << endl;
}
2unordered_set存儲s2
unordered_set使用
是 C++ STL 提供的 無序集合，底層使用 哈希表 實現，支持 O(1) 平均時間復雜度 進行 插入、刪除、查找。
1. 基本用法
(1) 頭文件
#include <unordered_set>
(2) 聲明
unordered_set<int> mySet; // 存儲 int 類型
unordered_set<string> mySet2; // 存儲 string 類型
(3) 插入
mySet.insert(10);
mySet.insert(20);
(4) 遍歷
for (int num : mySet) { cout << num << " ";
}
?? 注意：
unordered_set無序存儲，遍歷順序 不確定。
2. 主要操作
(1) 插入元素
unordered_set<int> mySet;
mySet.insert(1);
mySet.insert(2);
(2) 查找元素
if (mySet.find(2) != mySet.end()) { cout << "2 存在" << endl;
} else { cout << "2 不存在" << endl;
}
find(x) != end()表示 找到 x，否則 未找到。
(3) 刪除元素
mySet.erase(2); // 刪除值為 2 的元素
(4) 統計個數
cout << mySet.size() << endl;
(5) 清空集合
mySet.clear();
3. 高級用法
(1) 使用 count(x) 判斷是否存在
if (mySet.count(2)) {cout << "2 存在" << endl;
} else {cout << "2 不存在" << endl;
}
count(x)返回 0（不存在）或 1（存在）。
(2) 迭代器遍歷
for (auto it = mySet.begin(); it != mySet.end(); ++it) {cout << *it << " ";
}
4. 時間復雜度
| 操作 | 平均時間復雜度 |
|---|---|
insert(x) | O(1) |
find(x) | O(1) |
erase(x) | O(1) |
| 遍歷 | O(n) |
5. 適用場景
? 快速去重：unordered_set 可以存儲唯一值，O(1) 查找是否存在。
? 快速查找：比 vector 或 set 更快的 O(1) 查找。
? 集合操作：常用于 字符刪除、重復元素去除 等。
- 使用 unordered_set 來加速字符匹配，使得刪除操作的時間復雜度從優化到 O(n)。
- set的查詢速度為O(1)
- 使用writeIndex保存s1要寫入的位置
- 在存儲s2的set里面查詢，是否存在對應字符，不存在的寫入s1前面
- 刪掉后續字符
#include <iostream>
#include <string>
#include <unordered_set>using namespace std;void dele(string& s1, const string& s2) {unordered_set<char> removeSet(s2.begin(), s2.end()); // Step 1: 用哈希表存儲 s2 中所有字符int writeIndex = 0; // Step 2: 記錄寫入位置for (int i = 0; i < s1.size(); i++) { // Step 3: 遍歷 s1if (!removeSet.count(s1[i])) { // Step 4: 如果 s1[i] 不在 s2 中s1[writeIndex++] = s1[i]; // Step 5: 把 s1[i] 寫入當前位置}}s1.erase(writeIndex); // Step 6: 刪除剩余部分
}int main() {string s1, s2;cin >> s1 >> s2;dele(s1, s2); // 調用刪除函數cout << s1 << endl; // 輸出修改后的 s1return 0;
}
)
