小红的回文串
思路
题目给了三种操作：拆分（w→vv，m→nn）、轴对称（b↔d，p↔q）、翻转（b↔q，d↔p，n↔u），问经过若干次操作后能不能变成回文串。
先别急着写代码，想想这些操作到底在干嘛？
第一步：找等价类。 把所有能互相转换的字符归成一组：
- b、d、p、q 通过轴对称和翻转可以互相转换，它们是一类
- n、u 通过翻转可以互换，它们是一类
- 其他字母各自独立
所以判断回文的时候，b 和 q 算"相同"，n 和 u 也算"相同"。
第二步：处理拆分操作。 w 可以拆成两个 v，m 可以拆成两个 n。注意这里改变了字符串长度！也就是说，w 可以选择保留原样，也可以展开成 vv。m 同理，可以保留或展开成 nn（属于 n/u 等价类）。
那怎么判断展开后能不能回文？直觉上用双指针从两头往中间匹配。但问题来了——遇到 w 或 m 的时候，展不展开会影响后续的对齐方式，这就有了分支选择。
第三步：DFS + 记忆化。 用左指针 L 和右指针 R 从两端向中间推进，每一步从两侧各取一个字符（归一化后）进行比较：
- 普通字符直接比较等价类
- 遇到 w 或 m，尝试"不展开"和"展开"两种策略
- 展开后会产生一个"缓冲字符"（第二个 v 或 n），下一步优先消耗缓冲
状态是 (L, R, 左缓冲, 右缓冲)，用哈希表做记忆化，避免重复搜索。
基准情况：
- L > R 且缓冲都空 → 匹配完毕，是回文
- L > R 且只剩一个缓冲 → 奇数长度中间字符，也行
- L > R 且两个缓冲都有 → 两个缓冲必须相同
- L == R 且无缓冲 → 中间单字符，任何字符都行
代码
#include <bits/stdc++.h>
using namespace std;
int charClass(char c) {
if (c == 'b' || c == 'd' || c == 'p' || c == 'q') return 1;
if (c == 'n' || c == 'u') return 2;
if (c == 'v') return 3;
if (c == 'w') return 4;
if (c == 'm') return 5;
return c + 10;
}
bool solve(const string& s) {
int n = s.size();
if (n <= 1) return true;
auto bufCode = [](int b) -> int {
if (b == 0) return 0;
if (b == 2) return 1;
return 2;
};
unordered_map<long long, int> memo;
auto encode = [&](int L, int R, int lb, int rb) -> long long {
return ((long long)L * (n + 1) + R) * 9 + bufCode(lb) * 3 + bufCode(rb);
};
function<bool(int, int, int, int)> dfs = [&](int L, int R, int lb, int rb) -> bool {
if (L > R) {
if (lb == 0 && rb == 0) return true;
if (lb == 0 || rb == 0) return true;
return lb == rb;
}
if (L == R && lb == 0 && rb == 0) return true;
long long key = encode(L, R, lb, rb);
auto it = memo.find(key);
if (it != memo.end()) return it->second;
struct Opt { int cls, ptr, buf; };
vector<Opt> leftOpts, rightOpts;
if (lb != 0) {
leftOpts.push_back({lb, L, 0});
} else {
int cc = charClass(s[L]);
if (cc == 4) leftOpts = {{4, L+1, 0}, {3, L+1, 3}};
else if (cc == 5) leftOpts = {{5, L+1, 0}, {2, L+1, 2}};
else leftOpts = {{cc, L+1, 0}};
}
if (rb != 0) {
rightOpts.push_back({rb, R, 0});
} else {
int cc = charClass(s[R]);
if (cc == 4) rightOpts = {{4, R-1, 0}, {3, R-1, 3}};
else if (cc == 5) rightOpts = {{5, R-1, 0}, {2, R-1, 2}};
else rightOpts = {{cc, R-1, 0}};
}
bool res = false;
for (auto& lo : leftOpts) {
for (auto& ro : rightOpts) {
if (lo.cls == ro.cls && dfs(lo.ptr, ro.ptr, lo.buf, ro.buf)) {
res = true;
break;
}
}
if (res) break;
}
memo[key] = res;
return res;
};
return dfs(0, n - 1, 0, 0);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
cout << (solve(s) ? "YES" : "NO") << "\n";
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
static int n;
static String s;
static HashMap<Long, Boolean> memo;
static int charClass(char c) {
if (c == 'b' || c == 'd' || c == 'p' || c == 'q') return 1;
if (c == 'n' || c == 'u') return 2;
if (c == 'v') return 3;
if (c == 'w') return 4;
if (c == 'm') return 5;
return c + 10;
}
static int bufCode(int b) {
if (b == 0) return 0;
if (b == 2) return 1;
return 2;
}
static long encode(int L, int R, int lb, int rb) {
return ((long) L * (n + 1) + R) * 9 + bufCode(lb) * 3 + bufCode(rb);
}
static boolean dfs(int L, int R, int lb, int rb) {
if (L > R) {
if (lb == 0 && rb == 0) return true;
if (lb == 0 || rb == 0) return true;
return lb == rb;
}
if (L == R && lb == 0 && rb == 0) return true;
long key = encode(L, R, lb, rb);
if (memo.containsKey(key)) return memo.get(key);
int[][] leftOpts, rightOpts;
if (lb != 0) {
leftOpts = new int[][]{{lb, L, 0}};
} else {
int cc = charClass(s.charAt(L));
if (cc == 4) leftOpts = new int[][]{{4, L+1, 0}, {3, L+1, 3}};
else if (cc == 5) leftOpts = new int[][]{{5, L+1, 0}, {2, L+1, 2}};
else leftOpts = new int[][]{{cc, L+1, 0}};
}
if (rb != 0) {
rightOpts = new int[][]{{rb, R, 0}};
} else {
int cc = charClass(s.charAt(R));
if (cc == 4) rightOpts = new int[][]{{4, R-1, 0}, {3, R-1, 3}};
else if (cc == 5) rightOpts = new int[][]{{5, R-1, 0}, {2, R-1, 2}};
else rightOpts = new int[][]{{cc, R-1, 0}};
}
boolean res = false;
for (int[] lo : leftOpts) {
for (int[] ro : rightOpts) {
if (lo[0] == ro[0] && dfs(lo[1], ro[1], lo[2], ro[2])) {
res = true;
break;
}
}
if (res) break;
}
memo.put(key, res);
return res;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
s = br.readLine().trim();
n = s.length();
memo = new HashMap<>();
sb.append(dfs(0, n - 1, 0, 0) ? "YES" : "NO").append('\n');
}
System.out.print(sb);
}
}
import sys
input = sys.stdin.readline
def char_class(c):
if c in 'bdpq':
return 1
if c in 'nu':
return 2
if c == 'v':
return 3
if c == 'w':
return 4
if c == 'm':
return 5
return ord(c) + 10
def solve(s):
n = len(s)
if n <= 1:
return True
memo = {}
def buf_code(b):
if b == 0: return 0
if b == 2: return 1
return 2
def dfs(L, R, lb, rb):
if L > R:
if lb == 0 and rb == 0:
return True
if lb == 0 or rb == 0:
return True
return lb == rb
if L == R and lb == 0 and rb == 0:
return True
key = (L, R, buf_code(lb), buf_code(rb))
if key in memo:
return memo[key]
left_opts = []
if lb != 0:
left_opts.append((lb, L, 0))
else:
cc = char_class(s[L])
if cc == 4:
left_opts = [(4, L+1, 0), (3, L+1, 3)]
elif cc == 5:
left_opts = [(5, L+1, 0), (2, L+1, 2)]
else:
left_opts = [(cc, L+1, 0)]
right_opts = []
if rb != 0:
right_opts.append((rb, R, 0))
else:
cc = char_class(s[R])
if cc == 4:
right_opts = [(4, R-1, 0), (3, R-1, 3)]
elif cc == 5:
right_opts = [(5, R-1, 0), (2, R-1, 2)]
else:
right_opts = [(cc, R-1, 0)]
res = False
for lo in left_opts:
for ro in right_opts:
if lo[0] == ro[0] and dfs(lo[1], ro[1], lo[2], ro[2]):
res = True
break
if res:
break
memo[key] = res
return res
return dfs(0, n - 1, 0, 0)
t = int(input())
out = []
for _ in range(t):
s = input().strip()
out.append("YES" if solve(s) else "NO")
print('\n'.join(out))
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
function charClass(c) {
if (c === 'b' || c === 'd' || c === 'p' || c === 'q') return 1;
if (c === 'n' || c === 'u') return 2;
if (c === 'v') return 3;
if (c === 'w') return 4;
if (c === 'm') return 5;
return c.charCodeAt(0) + 10;
}
function bufCode(b) {
if (b === 0) return 0;
if (b === 2) return 1;
return 2;
}
function solve(s) {
const n = s.length;
if (n <= 1) return true;
const memo = new Map();
function encode(L, R, lb, rb) {
return ((L * (n + 1) + R) * 9 + bufCode(lb) * 3 + bufCode(rb));
}
function dfs(L, R, lb, rb) {
if (L > R) {
if (lb === 0 && rb === 0) return true;
if (lb === 0 || rb === 0) return true;
return lb === rb;
}
if (L === R && lb === 0 && rb === 0) return true;
const key = encode(L, R, lb, rb);
if (memo.has(key)) return memo.get(key);
let leftOpts, rightOpts;
if (lb !== 0) {
leftOpts = [[lb, L, 0]];
} else {
const cc = charClass(s[L]);
if (cc === 4) leftOpts = [[4, L+1, 0], [3, L+1, 3]];
else if (cc === 5) leftOpts = [[5, L+1, 0], [2, L+1, 2]];
else leftOpts = [[cc, L+1, 0]];
}
if (rb !== 0) {
rightOpts = [[rb, R, 0]];
} else {
const cc = charClass(s[R]);
if (cc === 4) rightOpts = [[4, R-1, 0], [3, R-1, 3]];
else if (cc === 5) rightOpts = [[5, R-1, 0], [2, R-1, 2]];
else rightOpts = [[cc, R-1, 0]];
}
let res = false;
for (const lo of leftOpts) {
for (const ro of rightOpts) {
if (lo[0] === ro[0] && dfs(lo[1], ro[1], lo[2], ro[2])) {
res = true;
break;
}
}
if (res) break;
}
memo.set(key, res);
return res;
}
return dfs(0, n - 1, 0, 0);
}
const t = parseInt(lines[0]);
const output = [];
for (let i = 1; i <= t; i++) {
output.push(solve(lines[i]) ? "YES" : "NO");
}
console.log(output.join("\n"));
});
复杂度分析
- 时间复杂度:
均摊。虽然状态空间理论上是
，但双指针只会向中间收拢，实际可达状态数与字符串长度线性相关。
- 空间复杂度:
小结
这题的核心不在于回文判断本身，而在于理清字符之间的等价关系。把 b/d/p/q 归为一类、n/u 归为一类，这一步想明白了，问题就清晰很多。难点在于 w→vv 和 m→nn 的拆分会改变串长，导致左右两侧的对齐方式有多种可能，需要用 DFS 配合记忆化来搜索。状态设计上，用一个"缓冲区"来记录拆分后还没消耗的那个字符，就把问题拆解得很干净了。
京公网安备 11010502036488号