Java 字符串回文判断：拆分、轴对称、翻转

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

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

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

输入描述

第一行输入一个整数 T 表示询问次数接下来 T 行，每行输入一个字符串表示询问。

输出描述

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

解题思路

首先判断字符串的长度是否为偶数，如果为奇数，则不可能构成回文串，直接输出“NO”；
对于每个字符串，首先判断是否可以通过拆分操作变成回文串。如果一个字符的个数为奇数且大于等于3，则不可能通过拆分操作变成回文串，直接输出“NO”；
如果字符串经过拆分操作后仍然无法构成回文串，则判断是否可以通过轴对称和翻转操作变成回文串。遍历字符串的前一半字符，如果存在一个字符不能通过轴对称和翻转操作变成回文串的字符，则输出“NO”；否则输出“YES”。

代码实现如下：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        scanner.nextLine();
        while (t > 0) {
            String str = scanner.nextLine();
            int len = str.length();
            if (len % 2 == 1) {
                System.out.println("NO");
                t--;
                continue;
            }
            int[] count = new int[26];
            for (int i = 0; i < len; i++) {
                char ch = str.charAt(i);
                count[ch - 'a']++;
            }
            boolean canSplit = true;
            for (int i = 0; i < 26; i++) {
                if (count[i] % 2 == 1 && count[i] >= 3) {
                    canSplit = false;
                    break;
                }
            }
            if (!canSplit) {
                System.out.println("NO");
                t--;
                continue;
            }
            boolean canConvert = true;
            for (int i = 0; i < len / 2; i++) {
                char ch1 = str.charAt(i);
                char ch2 = str.charAt(len - i - 1);
                if ((ch1 == 'b' && ch2 != 'd') || (ch1 == 'p' && ch2 != 'q') || (ch1 == 'd' && ch2 != 'b') || (ch1 == 'q' && ch2 != 'p') || (ch1 == 'n' && ch2 != 'u') || (ch1 == 'u' && ch2 != 'n')) {
                    canConvert = false;
                    break;
                }
            }
            if (canConvert) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
            t--;
        }
    }
}

时间复杂度分析

对于每个字符串，需要遍历字符串的每个字符，统计字符的个数，时间复杂度为O(n)，其中n为字符串的长度。对于每个字符串，需要判断是否进行拆分操作和是否可以通过轴对称和翻转操作变成回文串，时间复杂度为O(n/2)，即O(n)。因此，总的时间复杂度为O(n)。