回文字符串

2026-03-26 暂无评论

全文共 296 字，阅读约 1 分钟

蓝桥杯2024省赛-回文字符串

题目描述

给定一个只包含小写字母的字符串 S，可以在字符串的开头加入任意数目的指定字符 l、q、b。问是否能通过这种方式将 S 转化为一个回文字符串。

输入格式

第一行一个整数 T，表示数据组数。
接下来 T 行，每行一个字符串 S。

输出格式

输出 T 行，每行 Yes 或 No。

样例

输入：

3
gmgqlq
pdlbll
aaa

输出：

Yes
No
Yes

解题思路

核心思想

由于只能在开头添加字符，因此：

如果字符串本身是回文，直接输出 Yes
否则，从两端向中间比较：
- 如果两端字符相等，继续向中间移动
- 如果不相等，检查右边字符是否属于 {l, q, b}，如果是，则跳过该字符（相当于在开头补了相同的字符），继续比较
- 否则，无法构成回文

双指针模拟

def check(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] == s[j]:
            i += 1
            j -= 1
        else:
            # 右边字符是指定字符，跳过（相当于在左边补了它）
            if s[j] in {'l', 'q', 'b'}:
                j -= 1
            else:
                return False
    return True

复杂度分析

时间复杂度：O(|S|)，每组数据只需一次遍历
空间复杂度：O(1)

完整代码

import os
import sys

letter = {'l', 'q', 'b'}

t = int(input())

def check(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] == s[j]:
            i += 1
            j -= 1
        else:
            if s[j] in letter:
                j -= 1
            else:
                return False
    return True

for _ in range(t):
    s = input()
    if s == s[::-1]:
        print('Yes')
    else:
        print('Yes' if check(s) else 'No')