小红的回文串

[编程题]小红的回文串

热度指数：2141 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

拆分。把 'w' 拆成2个 'v'，’m‘ 拆成 2个 'n'。
轴对称。把 'b' 轴对称成 'd' ，'p' 轴对称成 'q'，反之亦然。
翻转。把 'b' 翻转成'q'，把 'd' 翻转成 'p'，把' n' 翻转成 'u'，反之亦然。

经过若干次操作后，小红想知道这个字符串能不能变成回文串。

输入描述:

第一行输入一个整数  表示询问次数。

接下来  行，每行输入一个字符串表示询问。

所有字符串长度之和不超过  。

输出描述:

输出  行，每行输出 "YES" 或 "NO" 表示是否可以变成回文串。

示例1

输入

5
wovv
bod
pdd
moom
lalalai

输出

YES
YES
YES
YES
NO

说明

第一个字符串可以变成：vvovv（将第一个w拆成两个v）
第二个字符串可以变成：bob、dod、pop或qoq
第三个字符串可以变成：bdb
第四个字符串本来就是回文的，不用进行操作
第五个字符串不可以变成回文串

算法知识视频讲解

Java

BraveCoder

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while (T-- > 0) {
            String str = in.next();
            String str1 = str.replace("m", "nn");
            String str2 = str1.replace("w", "vv");
            int len = str2.length();
            boolean flag = true;
            for (int i = 0; i < len / 2; i++) {
                char c1 = str2.charAt(i);
                char c2 = str2.charAt(str2.length() - i - 1);
                if ((c1 == 'b' || c1 == 'd' || c1 == 'p' || c1 == 'q') && (c2 ==    'b' || c2 == 'd' || c2 == 'p' || c2 == 'q')) continue;
                if ((c1 == 'n' || c1 == 'u') && (c2 == 'n' || c2 == 'u')) continue;
                if (c1 != c2) {
                    flag = false;
                    break;
                }
            }
            if (flag) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

发表于 2025-08-29 12:23:18 回复(0)

Java

333lll

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static final Set<Character> set1 = new HashSet<>();
    private static final Set<Character> set2 = new HashSet<>();
    static {
        set1.add('d');
        set1.add('p');
        set1.add('q');
        set1.add('b');
        set2.add('u');
        set2.add('n');
    }
    private static String s;
    private static int i ,j;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            s = in.next();
            i = 0;
            j = s.length() - 1;
            System.out.println(f() ? "YES" : "NO");
        }
    }
    private static boolean f() {
        while (i <= j && ((s.charAt(i) == s.charAt(j)) || judge())) {
            i++;
            j--;
        }
        return i >= j;
    }
    private static boolean judge() {
        if (set1.contains(s.charAt(i)) && set1.contains(s.charAt(j))) return true;
        else if (set2.contains(s.charAt(i)) && set2.contains(s.charAt(j))) return true;
        else if (set1.contains(s.charAt(i)) || set1.contains(s.charAt(j))) return false;
        else {
            StringBuffer sb = new StringBuffer();
            if (s.charAt(i) == 'w' && s.charAt(j) == 'v') {

                sb.append(s, 0, i);
                sb.append("vv");
                ++j;
                s = sb.toString() + s.substring(i + 1);
                return true;
            } else if (s.charAt(i) == 'v' && s.charAt(j) == 'w') {

                sb.append(s.substring(0, j));
                sb.append("vv");
                s = sb.toString() + s.substring(j + 1);
                ++j;

                return true;
            } else if (s.charAt(i) == 'm' && (s.charAt(j) == 'n' || s.charAt(j) == 'u')) {

                sb.append(s.substring(0, i));
                sb.append("nn");

                ++j;
                s = sb.toString() + s.substring(i + 1);
                return true;
            } else if (s.charAt(j) == 'm' && (s.charAt(i) == 'n' || s.charAt(i) == 'u')) {
                sb.append(s.substring(0, j));
                sb.append("nn");
                s = sb.toString() + s.substring(j + 1);
                ++j;

                return true;
            } else return false;
        }


    }
}
//b d q p
//w -> v v
//m -> u u n n u n

发表于 2025-06-26 17:08:49 回复(0)

提交观点

问题信息

字符串模拟小红书双指针

难度：

2条回答 26收藏 891浏览

小红的回文串

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题