题目链接

小红的回文串

题目描述

小红有一个字符串，她可以对字符串进行若干次以下操作：

  1. 拆分：'w' "vv"，'m' "nn"。
  2. 轴对称：'b' 'd'，'p' 'q'。
  3. 翻转：'b' 'q'，'d' 'p'，'n' 'u'。

判断给定的字符串是否能通过这些操作变成一个回文串。

解题思路

本题的关键在于识别哪些字符可以通过操作相互转换，以及如何处理改变字符串长度的操作。

1. 字符等价类分析 首先，我们分析不改变字符串长度的操作（轴对称和翻转），找出哪些字符是“等价”的。

  • 'b' 'd' (轴对称)
  • 'b' 'q' (翻转)
  • 'd' 'p' (翻转)
  • 'p' 'q' (轴对称) 从以上关系可以看出，'b', 'd', 'p', 'q' 这四个字符可以相互转换，因此它们属于同一个等价类。
  • 'n' 'u' (翻转) 这两个字符可以相互转换，属于另一个等价类。
  • 其他未在操作中提及的字符（如 'o', 'v', 'a' 等）只能与自身匹配，各自构成一个只包含自己的等价类。

2. 规范化字符串 “拆分”操作 ('w' "vv", 'm' "nn") 会改变字符串的长度，这使得直接在原字符串上使用双指针判断变得困难。为了解决这个问题，我们可以先对原字符串进行一次规范化处理：遍历原字符串，将所有的 'w' 替换为 "vv"，'m' 替换为 "nn"，生成一个新的、长度固定的字符串。

3. 双指针回文判断 对这个规范化后的新字符串，我们就可以使用经典的双指针法来判断其是否能构成回文串了。

  • 设置左右指针 和 ，分别指向新字符串的头部和尾部。
  • 当 时，循环比较 和 指向的两个字符。
  • 如果两个字符属于同一个等价类（例如，一个是 'b'，另一个是 'q'），则我们认为它们是匹配的，将两个指针向中间移动（++, --）。
  • 如果两个字符不属于任何相同的等价类，那么无论如何操作，它们都无法匹配。这意味着该字符串不可能变成回文串，可以直接判定为 "NO"。
  • 如果循环正常结束，说明所有对应位置的字符都可以通过操作变成匹配的字符，因此可以构成回文串，判定为 "YES"。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 判断两个字符是否等价
bool are_equivalent(char c1, char c2) {
    if (c1 == c2) return true;
    string group1 = "bdpq";
    string group2 = "nu";
    if (group1.find(c1) != string::npos && group1.find(c2) != string::npos) {
        return true;
    }
    if (group2.find(c1) != string::npos && group2.find(c2) != string::npos) {
        return true;
    }
    return false;
}

void solve() {
    string s;
    cin >> s;

    // 1. 规范化字符串
    string t = "";
    for (char c : s) {
        if (c == 'w') {
            t += "vv";
        } else if (c == 'm') {
            t += "nn";
        } else {
            t += c;
        }
    }

    // 2. 双指针判断
    int l = 0, r = t.length() - 1;
    bool possible = true;
    while (l < r) {
        if (!are_equivalent(t[l], t[r])) {
            possible = false;
            break;
        }
        l++;
        r--;
    }

    if (possible) {
        cout << "YES" << '\n';
    } else {
        cout << "NO" << '\n';
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    // 判断两个字符是否等价
    private static boolean areEquivalent(char c1, char c2) {
        if (c1 == c2) return true;
        String group1 = "bdpq";
        String group2 = "nu";
        if (group1.indexOf(c1) != -1 && group1.indexOf(c2) != -1) {
            return true;
        }
        if (group2.indexOf(c1) != -1 && group2.indexOf(c2) != -1) {
            return true;
        }
        return false;
    }

    public static void solve(Scanner sc) {
        String s = sc.next();

        // 1. 规范化字符串
        StringBuilder tBuilder = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == 'w') {
                tBuilder.append("vv");
            } else if (c == 'm') {
                tBuilder.append("nn");
            } else {
                tBuilder.append(c);
            }
        }
        String t = tBuilder.toString();

        // 2. 双指针判断
        int l = 0, r = t.length() - 1;
        boolean possible = true;
        while (l < r) {
            if (!areEquivalent(t.charAt(l), t.charAt(r))) {
                possible = false;
                break;
            }
            l++;
            r--;
        }

        if (possible) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

def are_equivalent(c1, c2):
    """判断两个字符是否等价"""
    if c1 == c2:
        return True
    group1 = "bdpq"
    group2 = "nu"
    if c1 in group1 and c2 in group1:
        return True
    if c1 in group2 and c2 in group2:
        return True
    return False

def solve():
    s = input()
    
    # 1. 规范化字符串
    t = s.replace('w', 'vv').replace('m', 'nn')
    
    # 2. 双指针判断
    l, r = 0, len(t) - 1
    possible = True
    while l < r:
        if not are_equivalent(t[l], t[r]):
            possible = False
            break
        l += 1
        r -= 1
        
    if possible:
        print("YES")
    else:
        print("NO")

t = int(input())
for _ in range(t):
    solve()

算法及复杂度

  • 算法：字符串处理 + 双指针
  • 时间复杂度：对于每个测试用例，设其初始长度为 。规范化后的字符串长度最长为 。规范化过程需要 ，双指针判断需要 。因此，对于每个测试用例，时间复杂度为 。总时间复杂度为 。
  • 空间复杂度：需要存储规范化后的字符串，其长度最大为输入字符串的两倍。因此，空间复杂度为 。