题目链接

小红的对称串

题目描述

小红定义一个字符串是轴对称的，当且仅当该字符串镜面翻转后和原串相同。例如，bod、pwq、ovo 等字符串是轴对称的，而 ntn 则不是轴对称的。

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

提示：单个轴对称的字母有：ilmnouvwx，一对相互轴对称的字母有 p 和 q、b 和 d。

输入:

  • 第一行输入一个正整数，代表询问次数。
  • 接下来的行，每行输入一个仅由小写字母组成的字符串，长度不超过 。

输出:

  • 对于每个询问，如果该字符串轴对称，则输出 Yes；否则输出 No。

解题思路

这是一个字符串处理问题，我们需要判断给定的字符串是否满足轴对称的性质：

  1. 首先，我们需要明确轴对称的规则：

    • 单个字母自身对称的有：i、l、m、n、o、u、v、w、x。
    • 互相对称的字母对有：p 和 q、b 和 d。
    • 其他字母都不是对称的。

  2. 判断方法：

    • 从字符串两端向中间比较。
    • 左边第 个字符与右边第 个字符必须满足对称关系。
    • 如果某一对字符不满足对称关系，则整个字符串不是轴对称的。

  3. 具体实现：

    • 创建一个映射表，指定每个字符的对称字符。
    • 使用双指针法，从两端向中间遍历并比较。

代码

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 构建对称字符映射表
    map<char, char> sym_map;
    string self_sym = "ilmnouvwx";
    for (char c : self_sym) {
        sym_map[c] = c;
    }
    sym_map['b'] = 'd';
    sym_map['d'] = 'b';
    sym_map['p'] = 'q';
    sym_map['q'] = 'p';
    
    while (n--) {
        string s;
        cin >> s;
        
        bool is_symmetric = true;
        int left = 0, right = s.length() - 1;
        
        while (left <= right) {
            // 检查当前字符是否在映射表中，且是否与对应位置的字符满足对称关系
            if (sym_map.find(s[left]) == sym_map.end() || sym_map[s[left]] != s[right]) {
                is_symmetric = false;
                break;
            }
            left++;
            right--;
        }
        
        cout << (is_symmetric ? "Yes" : "No") << endl;
    }
    
    return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 构建对称字符映射表
        Map<Character, Character> symMap = new HashMap<>();
        String selfSym = "ilmnouvwx";
        for (int i = 0; i < selfSym.length(); i++) {
            char c = selfSym.charAt(i);
            symMap.put(c, c);
        }
        symMap.put('b', 'd');
        symMap.put('d', 'b');
        symMap.put('p', 'q');
        symMap.put('q', 'p');
        
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            
            boolean isSymmetric = true;
            int left = 0, right = s.length() - 1;
            
            while (left <= right) {
                char leftChar = s.charAt(left);
                char rightChar = s.charAt(right);
                
                if (!symMap.containsKey(leftChar) || symMap.get(leftChar) != rightChar) {
                    isSymmetric = false;
                    break;
                }
                left++;
                right--;
            }
            
            System.out.println(isSymmetric ? "Yes" : "No");
        }
    }
}

n = int(input())

# 构建对称字符映射表
sym_map = {}
self_sym = "ilmnouvwx"
for c in self_sym:
    sym_map[c] = c

sym_map['b'] = 'd'
sym_map['d'] = 'b'
sym_map['p'] = 'q'
sym_map['q'] = 'p'

for _ in range(n):
    s = input().strip()
    
    is_symmetric = True
    left, right = 0, len(s) - 1
    
    while left <= right:
        if s[left] not in sym_map or sym_map[s[left]] != s[right]:
            is_symmetric = False
            break
        left += 1
        right -= 1
    
    print("Yes" if is_symmetric else "No")

算法及复杂度

  • 算法：双指针 + 哈希表。
  • 时间复杂度：，其中 是询问次数， 是字符串的平均长度。
  • 空间复杂度：，哈希表的大小是固定的，仅包含特定的对称字符。