题解 | 小红的回文串

b,d,p,q可以视为等价，麻烦的是对m的处理，由于m拆分后的n有等价类，所以在匹配的时候需要给u考虑进去！！！

这里有两种办法：

1（不推荐）：是等到匹配的时候处理，这里有个很ex人的地方，那就是n的等价类，n和u等价，那么在两个字符比较的时候如果一边是u另一边是m，那么这个m需要拆（我就是这里没有想到，被卡了很久）。

#include<iostream>
using namespace std;

bool judge(string s) {
    int j = s.length() - 1;
    for (int i = 0; i < j; i++) {
        if (s[i] != s[j]) {
            return false;
        } else {
            j--;
        }
    }
    return true;
}

void solve() {
    string s;
    cin >> s;
    if (s.empty() || judge(s)) {
        cout << "YES" << endl;
        return;
    }
    //1 1 2 3
    //0 1 2 3
    int j = s.length() - 1;
    for (int i = 0; i < j; i++, j--) {
        if (s[i] != s[j]) {
            if (s[i] == 'w' || s[i] == 'v') {
                if (s[j] == 'v') {
                    s[i] = 'v';
                    s.insert(i + 1, 1, 'v');
                    j++;
                } else if (s[j] == 'w') {
                    s[j] = 'v';
                    s.insert(j, 1, 'v');
                    j++;
                } else {
                    cout << "NO" << endl;
                    return;
                }
            } else if (s[i] == 'm' || s[i] == 'n' || s[i] =='u') {
                if (s[j] == 'n' || s[j] == 'u') {
                    if(s[i]=='u'|| s[i] == 'n') {
                        continue;
                    }
                    s[i] = 'n';//s[i]等于m
                    s.insert(i + 1, 1, 'n');
                    j++;
                } else if (s[j] == 'm') {//这里s[i]等于n和等于u等效,都需要拆m
                    s[j] = 'n';
                    s.insert(j, 1, 'n');
                    j++;
                }else{
                    cout<<"NO"<<endl;
                    return ;
                }
            }
            else if (s[i] == 'b' || s[i] == 'd' || s[i] == 'p' || s[i] == 'q') {
                if (s[j] == 'b' || s[j] == 'd' || s[j] == 'p' || s[j] == 'q') {
                    continue;
                }
                cout << "NO" << endl;
                return;
            } else {
                cout << "NO" << endl;
                return;
            }
        }
    }
    cout << "YES" << endl;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

由上面一种解法得出的结论：最好还是先给能拆的拆了，这样就不会出错了

于是有了解法2：

#include<iostream>
using namespace std;

bool judge(string s){
    int j = s.length()-1;
    for(int i=0;i<j;i++){
        if(s[i]!=s[j]){
            return false;
        }else{
            j--;
        }
    }
    return true;
}

void solve(){
    string s;
    cin>>s;
    int num =0;//表示拆开后新增的数量
    for(int i=0;i<s.length()+num;i++){
        if(s[i]=='w'){
            s[i] ='v';
            s.insert(i,1,'v');
            i++;
            num++;
        }else if(s[i] == 'm'){
            s[i] ='n';
            s.insert(i,1,'n');
            i++;
            num++;
        }

    }
    if(s.empty() || judge(s)){
        cout<<"YES"<<endl;
        return;
    }
    //1 1 2 3
    //0 1 2 3
    int j = s.length()-1;
    for(int i=0;i<j;i++,j--){
        if(s[i]!=s[j]){
            if(s[i] =='b' ||s[i] =='d' || s[i] =='p' || s[i] =='q'){
                if(s[j] =='b' ||s[j] =='d' || s[j] =='p' || s[j] =='q'){
                    continue;
                }
                cout<<"NO"<<endl;
                return;
            }
            else if(s[i] =='n' || s[i] == 'u'){
                if(s[j] =='n' || s[j] == 'u'){
                    continue;
                }
                cout<<"NO"<<endl;
                return;
            }else{
                cout<<"NO"<<endl;
                return;
            }
        }else{
            
        }
    }
    cout<<"YES"<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}