小红的对称串

[题目链接](https://www.nowcoder.com/practice/9719e6db0bbd41b6bbf5c8052430b1f5)

思路

本题要求判断一个字符串是否"轴对称"，即镜面翻转后与原串相同。

什么是轴对称？

把字符串想象成写在纸上，沿中轴进行左右翻转（镜像）。翻转后，字符的顺序会反过来，同时每个字母本身也会发生镜像变换。因此一个字符串轴对称，等价于：将每个字符替换为它的镜像字符后，整个串是回文的。

字符的镜像关系

题目给出了两类信息：

  1. 自身轴对称的字母：i, l, m, n, o, u, v, w, x，这些字母镜像翻转后还是自己。
  2. 互为镜像的字母对：b <-> d，p <-> q。

其余字母没有镜像对应，包含它们的字符串一定不是轴对称的。

判断方法

建立一个镜像映射表 ，然后使用双指针从两端向中间逐一检查：对于位置 和位置 ，需要满足 。

以样例 bpovoqd 为例：

  • = b， = d，，匹配。
  • = p， = q，，匹配。
  • = o， = o，，匹配。
  • = v，中间位置，，匹配。

所以输出 Yes。

而 bbbb： = b， = b，，不匹配，输出 No。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    char mir[128];
    memset(mir, 0, sizeof(mir));
    string self = "ilmnouvwx";
    for(char c : self) mir[(int)c] = c;
    mir['p'] = 'q'; mir['q'] = 'p';
    mir['b'] = 'd'; mir['d'] = 'b';

    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        int n = s.size();
        bool ok = true;
        for(int i = 0; i < n; i++){
            if(mir[(int)s[i]] != s[n-1-i]){
                ok = false;
                break;
            }
        }
        cout << (ok ? "Yes" : "No") << "\n";
    }
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] mir = new char[128];
        String self = "ilmnouvwx";
        for (char c : self.toCharArray()) mir[c] = c;
        mir['p'] = 'q'; mir['q'] = 'p';
        mir['b'] = 'd'; mir['d'] = 'b';

        int t = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            String s = sc.next();
            int n = s.length();
            boolean ok = true;
            for (int i = 0; i < n; i++) {
                if (mir[s.charAt(i)] != s.charAt(n - 1 - i)) {
                    ok = false;
                    break;
                }
            }
            sb.append(ok ? "Yes" : "No").append("\n");
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

mir = {}
for c in "ilmnouvwx":
    mir[c] = c
mir['p'] = 'q'
mir['q'] = 'p'
mir['b'] = 'd'
mir['d'] = 'b'

t = int(input())
out = []
for _ in range(t):
    s = input().strip()
    n = len(s)
    ok = True
    for i in range(n):
        if mir.get(s[i], '') != s[n-1-i]:
            ok = False
            break
    out.append("Yes" if ok 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.trim()));
rl.on('close', () => {
    const mir = {};
    for (const c of "ilmnouvwx") mir[c] = c;
    mir['p'] = 'q'; mir['q'] = 'p';
    mir['b'] = 'd'; mir['d'] = 'b';

    const t = parseInt(lines[0]);
    const res = [];
    for (let i = 1; i <= t; i++) {
        const s = lines[i];
        const n = s.length;
        let ok = true;
        for (let j = 0; j < n; j++) {
            if ((mir[s[j]] || '') !== s[n - 1 - j]) {
                ok = false;
                break;
            }
        }
        res.push(ok ? "Yes" : "No");
    }
    console.log(res.join('\n'));
});

复杂度分析

  • 时间复杂度：，其中 是询问次数， 是字符串长度。每个字符串线性扫描一次。
  • 空间复杂度：，存储输入字符串。