当前位置：首页 > article >正文

37.构造回文字符串问题|Marscode AI刷题

article 2025/1/22 12:57:15

1.题目

问题描述

小C手中有一个由小写字母组成的字符串 s。她希望构造另一个字符串 t，并且这个字符串需要满足以下几个条件：

t 由小写字母组成，且长度与 s 相同。
t 是回文字符串，即从左到右与从右到左读取相同。
t 的字典序要小于 s，并且在所有符合条件的字符串中字典序尽可能大。

小C想知道是否能构造出这样的字符串 t，输出这样的t。如果无法构造满足条件的字符串，则输出 -1。

测试样例

样例1：

输入：s = "abc"

输出：'aba'

样例2：

输入：s = "cba"

输出：'cac'

样例3：

输入：s = "aaa"

输出：'-1'

2.思路

构造回文字符串：
- 首先，我们需要构造一个字典序最大的回文字符串 t。回文字符串的特点是从左到右和从右到左相同。因此，我们可以通过复制字符串的一半来构造回文字符串，保证回文性质。
判断构造的回文是否满足条件：
- 构造的回文字符串 t 字典序应该小于原始字符串 s，如果满足这个条件，就可以直接返回 t。
调整字典序：
- 如果通过构造回文字符串得到的 t 字典序不满足 t < s，则需要从回文的中间位置开始尝试逐步减小字典序。
- 从回文的中心开始，向左逐步调整字符，使得它们比原本的字符小，从而保证字典序尽可能大，但依然小于 s。
返回结果：
- 如果能够找到符合条件的回文字符串 t，则返回它；如果无法调整使得字典序小于 s，则返回 1。

3.代码

def solution(s: str) -> str:
    # 将输入字符串转为列表方便操作
    s = list(s)
    n = len(s)

    # 定义一个函数，用于将字符串调整为回文字符串
    def build(t):
        s = t.copy()  # 复制 t，避免修改原始列表
        l, r = 0, n - 1  # 定义双指针，左指针从0开始，右指针从n-1开始
        # 使用双指针构造回文
        while l < r:
            s[r] = s[l]  # 将左侧字符赋值给右侧
            l += 1
            r -= 1
        return s

    # 尝试直接将 s 构造成回文字符串
    t = build(s)
    if t < s:  # 如果构造的回文字符串字典序小于原字符串
        ans = t
    else:
        # 如果直接构造的回文不满足字典序小于 s 的条件
        # 从回文中心开始尝试减小字典序
        i = (n - 1) >> 1  # 确定中间位置，向左遍历
        while i >= 0:
            if s[i] == 'a':  # 如果当前字符为 'a'
                s[i] = 'z'  # 将其变为 'z'
            else:
                s[i] = chr(ord(s[i]) - 1)  # 将当前字符减小一个字母
                break  # 减小成功后退出循环
            i -= 1  # 向左移动指针
        if i == -1:  # 如果遍历完成仍无法减小字典序
            ans = ["-1"]  # 无法构造符合条件的字符串
        else:
            # 成功减小字典序后，重新构造回文
            ans = build(s)
    return "".join(ans)  # 返回最终结果，将列表转为字符串

# 测试用例
if __name__ == '__main__':
    # 测试样例1，输入 "abc"，期望输出 "aba"
    print(solution(s = "abc") == 'aba')  # 输出 True 表示通过测试
    # 测试样例2，输入 "cba"，期望输出 "cac"
    print(solution(s = "cba") == 'cac')  # 输出 True 表示通过测试
    # 测试样例3，输入 "aaa"，期望输出 "-1"
    print(solution(s = "aaa") == '-1')  # 输出 True 表示通过测试

i = (n - 1) >> 1

在代码中，i = (n - 1) >> 1 是一种计算字符串中间位置的常见方式，其中：

解释

位运算：>> 1 表示右移一位，即将一个数除以 2，向下取整。

例如：
- 5>>1=25 >> 1 = 25>>1=2 （整数除法结果）。
- 4>>1=24 >> 1 = 24>>1=2。
表达式含义：(n - 1) >> 1 计算了字符串 sss 的中心位置的索引：
- n−1n - 1n−1：字符串的最大索引位置。
- 右移一位相当于除以 2，得到中心索引位置。
- 这是一个向左偏的中心索引，适用于在字符串中以双指针的方式从中心向两边遍历。