h033 - 雜訊移除 (Noise)
題目描述
題目給定兩個字串 s 和 d，d 代表雜訊。目標是從 s 中移除所有在 d 中出現的字元，然後判斷剩餘的字串是否為迴文。
解題思路
解題思路是先遍歷字串 s，對於每個字元，檢查它是否在字串 d 中存在。如果不在 d 中，則將該字元添加到新的字串 a 中。最後，判斷字串 a 是否為迴文。迴文判斷使用雙指針從字串兩端向中間比較字元，如果所有字元都相同，則為迴文。
複雜度分析
- 時間複雜度: O(n*m + k)，其中 n 是字串 s 的長度，m 是字串 d 的長度，k 是字串 a 的長度。遍歷 s 需要 O(n)，每次檢查 s[i] 是否在 d 中需要 O(m)，迴文判斷需要 O(k)。
- 空間複雜度: O(k)，其中 k 是字串 a 的長度。
程式碼
#include <iostream>
using namespace std;
string s,d,a;
bool judge(string x){
for(int i=0,j=x.size()-1;i<x.size();++i,--j){
if(x[i]!=x[j])return 0;
}
return 1;
}
int main(){
cin >> s >> d;
for(int i=0;i<s.size();++i){
bool ac=1;
for(int j=0;j<d.size()&∾++j){
if(s[i]==d[j])ac=0;
}
if(ac)a+=s[i];
}
if(judge(a)){
cout << "Yes";
}
else{
cout << "No";
}
}