题解 | #小红的对称串#

题目链接

小红的对称串

题目描述

小红定义一个字符串是“轴对称的”，当且仅当该字符串镜面翻转后和原串相同。例如 bod 是轴对称的，因为 b 的镜像是 d，o 的镜像是自身。

给定的对称规则如下：

单个轴对称的字母有: "i", "l", "m", "o", "u", "v", "w", "x"。
相互轴对称的字母对有: 'p' 和 'q', 'b' 和 'd'。
注意：提示中明确指出 "n" 是自身对称的。样例 ntn 之所以结果为 "No"，是因为中间的字母 't' 不属于任何对称字符，破坏了对称性。

给定一个字符串，判断它是否是轴对称的。

解题思路

这个问题是对传统回文串判断的扩展，核心在于将字符的相等判断替换为题目定义的“轴对称”关系判断。最适合的算法是双指针法。

1. 建立对称关系映射

首先，我们需要清晰地定义出所有合法的对称关系。

自身对称字符集合：S = {'i', 'l', 'm', 'n', 'o', 'u', 'v', 'w', 'x'}
成对对称字符映射：M = {'p':'q', 'q':'p', 'b':'d', 'd':'b'}
任何不在此列的字符（如 'a', 'c', 'n' 等）都是非对称的。

2. 双指针算法

初始化两个指针，left 指向字符串的第一个字符（索引 0），right 指向最后一个字符（索引 len-1）。
进入一个循环，条件是 left <= right。在循环中，两个指针向中间靠拢。
在每一步，我们比较 char_left = s[left] 和 char_right = s[right]：
- 情况一：char_left == char_right
  - 如果两个字符相同，那么它们必须是自身对称的。我们检查 char_left 是否在自身对称字符集合 S 中。
  - 如果不在，说明出现了像 'a'=='a' 或 'n'=='n' 这样的情况，它们不是轴对称的。因此，字符串不满足条件，直接返回 "No"。
- 情况二：char_left != char_right
  - 如果两个字符不同，那么它们必须是一对成对对称的字符。我们检查 char_right 是否等于 M[char_left]。
  - 如果不等于（或者 char_left 根本不在映射 M 的键中），说明它们不是合法的对称对。因此，字符串不满足条件，直接返回 "No"。
如果当前这对字符通过了检查，则移动指针：left++，right--。
如果循环正常结束（即所有字符对都满足对称关系），则说明整个字符串是轴对称的，返回 "Yes"。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;

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

    set<char> self_symmetric = {'i', 'l', 'm', 'n', 'o', 'u', 'v', 'w', 'x'};
    map<char, char> pairs = {
        {'p', 'q'}, {'q', 'p'},
        {'b', 'd'}, {'d', 'b'}
    };

    int left = 0, right = s.length() - 1;
    bool is_symmetric = true;

    while (left <= right) {
        char char_left = s[left];
        char char_right = s[right];

        if (char_left == char_right) {
            if (self_symmetric.find(char_left) == self_symmetric.end()) {
                is_symmetric = false;
                break;
            }
        } else {
            if (pairs.find(char_left) == pairs.end() || pairs[char_left] != char_right) {
                is_symmetric = false;
                break;
            }
        }
        left++;
        right--;
    }

    if (is_symmetric) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.Set;
import java.util.Map;
import java.util.HashMap;

public class Main {
    private static final Set<Character> selfSymmetric = Set.of('i', 'l', 'm', 'n', 'o', 'u', 'v', 'w', 'x');
    private static final Map<Character, Character> pairs = new HashMap<>();
    
    static {
        pairs.put('p', 'q'); pairs.put('q', 'p');
        pairs.put('b', 'd'); pairs.put('d', 'b');
    }

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

    private static void solve(String s) {
        int left = 0;
        int right = s.length() - 1;
        boolean isSymmetric = true;

        while (left <= right) {
            char charLeft = s.charAt(left);
            char charRight = s.charAt(right);

            if (charLeft == charRight) {
                if (!selfSymmetric.contains(charLeft)) {
                    isSymmetric = false;
                    break;
                }
            } else {
                if (!pairs.containsKey(charLeft) || pairs.get(charLeft) != charRight) {
                    isSymmetric = false;
                    break;
                }
            }
            left++;
            right--;
        }

        if (isSymmetric) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

import sys

def solve():
    s = sys.stdin.readline().strip()

    self_symmetric = {'i', 'l', 'm', 'n', 'o', 'u', 'v', 'w', 'x'}
    pairs = {'p': 'q', 'q': 'p', 'b': 'd', 'd': 'b'}

    left, right = 0, len(s) - 1
    is_symmetric = True

    while left <= right:
        char_left = s[left]
        char_right = s[right]

        if char_left == char_right:
            if char_left not in self_symmetric:
                is_symmetric = False
                break
        else:
            if pairs.get(char_left) != char_right:
                is_symmetric = False
                break
        
        left += 1
        right -= 1

    if is_symmetric:
        print("Yes")
    else:
        print("No")


def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：双指针
时间复杂度： $O(T \cdot N)$ 。
- $T$ 是测试数据的组数。
- 对于每组数据，设字符串长度为 $N$ 。我们使用双指针法，最多遍历字符串的一半，因此处理一个字符串的时间复杂度为 $O(N)$ 。
空间复杂度： $O(1)$ 。
- 我们只需要常数额外的空间来存储对称关系的集合和映射，以及几个指针变量。这与输入字符串的长度无关。