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

1.题目

问题描述

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

1. t 由小写字母组成，且长度与 s 相同。
2. t 是回文字符串，即从左到右与从右到左读取相同。
3. 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 += 1r -= 1return s# 尝试直接将 s 构造成回文字符串t = build(s)if t < s:  # 如果构造的回文字符串字典序小于原字符串ans = telse:# 如果直接构造的回文不满足字典序小于 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. 位运算：>> 1 表示右移一位，即将一个数除以 2，向下取整。

   例如：

   • 5>>1=25 >> 1 = 25>>1=2 （整数除法结果）。
   • 4>>1=24 >> 1 = 24>>1=2。

2. 表达式含义：(n - 1) >> 1 计算了字符串 sss 的中心位置的索引：

   • n−1n - 1n−1：字符串的最大索引位置。
   • 右移一位相当于除以 2，得到中心索引位置。
   • 这是一个向左偏的中心索引，适用于在字符串中以双指针的方式从中心向两边遍历。

• 为什么’a’要变成’z’？ 如果字符已经是 'a'，你不能再减小它，因为 'a' 是字母表中的最小字符。这将意味着要将前一位字母减小一位，为了保证t在所有符合条件的字符串中字典序尽可能大，所以将’a'要变成’z'