題敘
https://toj.tfcis.org/oj/pro/274/
定義單錯誤迴文為一個字串中只除去一個字元後，剩下的字串為迴文
給一個字串，求該字串是否為單錯誤迴文
想法
對於一個字串 $s$ ，檢查其左右兩端 $L$ $R$
如果 $s[L] == s[R]$ 那麼就繼續檢查 $L+1$ 到 $R-1$
否則判斷 $L+1$ 到 $R$ 這個字串以及 $L$ 到 $R-1$ 這個字串誰是迴文
如果在這其中錯誤超過 $1$ 次，那就表示這不是單錯誤迴文
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int n;
string s;
bool check(int l,int r,int err){
for(;l<r;l++,r--){
if(s[l]==s[r])
continue;
else{
if(err==1) return false;
return check(l+1,r,err+1) || check(l,r-1,err+1);
}
}
}
int main(){
cin>>n;
while(n--){
cin>>s;
cout<<(check(0,s.size()-1,0) == true ? "YES\n" : "NO\n");
}
return 0;
}
|
複雜度分析
對於一個字串至多檢查全部
複雜度 $O(nlen(s))$