小红的回文串

[题目链接](https://www.nowcoder.com/practice/b0c3a7aecb0a47ab865602585f4402a7)

思路

题目允许对字符串进行三种操作：拆分（'w' -> 'vv'，'m' -> 'nn'）、轴对称（'b' <-> 'd'，'p' <-> 'q'）、翻转（'b' <-> 'q'，'d' <-> 'p'，'n' <-> 'u'）。问经过若干次操作后，字符串能否变成回文串。

等价字符分析

通过轴对称和翻转操作，可以得到以下等价关系：

• 'b' 可以变成 'd'（轴对称），'b' 可以变成 'q'（翻转），'d' 可以变成 'p'（翻转），因此 {b, d, p, q} 四个字符互相等价。
• 'n' 可以变成 'u'（翻转），因此 {n, u} 两个字符互相等价。

拆分操作改变长度

拆分操作会将一个字符变成两个字符：

• 'w' 拆成两个 'v'
• 'm' 拆成两个 'n'（等价于两个 'u'）

注意拆分操作是不可逆的，且会改变字符串长度。

归一化后判回文

核心思路是将原字符串展开并归一化：

1. 遇到 'w'，替换为 "vv"
2. 遇到 'm'，替换为 "nn"
3. 遇到 'b'、'd'、'p'、'q'，统一替换为同一个字符（如 'b'）
4. 遇到 'n'、'u'，统一替换为同一个字符（如 'n'）
5. 其他字符不变

展开归一化后，直接判断结果字符串是否是回文串即可。

正确性说明

• 拆分操作只能展开不能合并，所以 'w' 和 'm' 必须被拆分才有可能参与回文匹配。
• 'v' 不能合并成 'w'，所以两个相邻的 'v' 就是两个独立的 'v'。
• 同一等价类内的字符可以自由互换，所以归一化后只需检查对称位置是否属于同一等价类。

复杂度分析

• 时间复杂度：，每个字符串遍历两遍（展开一遍，回文判断一遍）。
• 空间复杂度：，存储展开后的字符串（最坏情况长度翻倍）。

代码

[sol-C++]

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        char buf[200005];
        scanf("%s", buf);
        string s(buf);
        // 展开并归一化
        string expanded;
        for(char c : s){
            if(c == 'w'){
                expanded += "vv";
            } else if(c == 'm'){
                expanded += "nn";
            } else if(c == 'b' || c == 'd' || c == 'p' || c == 'q'){
                expanded += 'b';
            } else if(c == 'n' || c == 'u'){
                expanded += 'n';
            } else {
                expanded += c;
            }
        }
        // 判回文
        int n = expanded.size();
        bool ok = true;
        for(int i = 0; i < n/2; i++){
            if(expanded[i] != expanded[n-1-i]){
                ok = false;
                break;
            }
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}

[sol-Java]

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while(t-- > 0){
            String s = br.readLine().trim();
            StringBuilder expanded = new StringBuilder();
            for(int i = 0; i < s.length(); i++){
                char c = s.charAt(i);
                if(c == 'w'){
                    expanded.append("vv");
                } else if(c == 'm'){
                    expanded.append("nn");
                } else if(c == 'b' || c == 'd' || c == 'p' || c == 'q'){
                    expanded.append('b');
                } else if(c == 'n' || c == 'u'){
                    expanded.append('n');
                } else {
                    expanded.append(c);
                }
            }
            String e = expanded.toString();
            int n = e.length();
            boolean ok = true;
            for(int i = 0; i < n/2; i++){
                if(e.charAt(i) != e.charAt(n-1-i)){
                    ok = false;
                    break;
                }
            }
            sb.append(ok ? "YES" : "NO").append('\n');
        }
        System.out.print(sb);
    }
}