回文字符串

2026-03-26 暂无评论

全文共 427 字，阅读约 2 分钟

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

题目描述

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

输入格式

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

输出格式

输出 T 行，每行 Yes 或 No。

样例

输入：

3
gmgqlq
pdlbll
aaa

输出：

Yes
No
Yes

解题思路

核心思想

只能在开头添加字符，新增字符必须与原串末尾的一段相对应。先统计开头连续的 l/q/b 个数 prefix，以及末尾连续的指定字符个数 suffix。全串都是指定字符时直接返回 Yes；否则 suffix 小于 prefix 时无解。

末尾保留 prefix 个字符，与原串开头配对；仅剥离末尾多出的 suffix-prefix 个字符，再判断留下的前缀是否回文。因为第一个和最后一个非指定字符的位置必须对称，需要剥离的数量是确定的。若剩余前缀为回文，在开头补上已剥离部分的逆序即可。

不能直接剥离整个末尾指定字符段：例如 lal 本来就是回文，应保留最后的 l。

不能在匹配完两端后继续跳过中间的不匹配字符，那相当于在原串内部插入字符。例如 alba 应输出 No。

双指针模拟

def check(s: str) -> bool:
    # 全是指定字符时，可在开头补上逆序串
    prefix = 0
    while prefix < len(s) and s[prefix] in "lqb":
        prefix += 1
    if prefix == len(s):
        return True
    # 末尾必须保留 prefix 个字符，与原串开头配对
    right = len(s) - 1
    while right >= 0 and s[right] in "lqb":
        right -= 1
    suffix = len(s) - 1 - right
    if suffix < prefix:
        return False
    right += prefix
    left = 0
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

复杂度分析

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

完整代码

import os
import sys

t = int(input())

def check(s: str) -> bool:
    # 全是指定字符时，可在开头补上逆序串
    prefix = 0
    while prefix < len(s) and s[prefix] in "lqb":
        prefix += 1
    if prefix == len(s):
        return True
    # 末尾必须保留 prefix 个字符，与原串开头配对
    right = len(s) - 1
    while right >= 0 and s[right] in "lqb":
        right -= 1
    suffix = len(s) - 1 - right
    if suffix < prefix:
        return False
    right += prefix
    left = 0
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

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