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

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.代码

1. def solution(s: str) -> str:
2.     # 将输入字符串转为列表方便操作
3.     s = list(s)
4.     n = len(s)
6.     # 定义一个函数，用于将字符串调整为回文字符串
7.     def build(t):
8.         s = t.copy()  # 复制 t，避免修改原始列表
9.         l, r = 0, n - 1  # 定义双指针，左指针从0开始，右指针从n-1开始
10.         # 使用双指针构造回文
11.         while l < r:
12.             s[r] = s[l]  # 将左侧字符赋值给右侧
13.             l += 1
14.             r -= 1
15.         return s
17.     # 尝试直接将 s 构造成回文字符串
18.     t = build(s)
19.     if t < s:  # 如果构造的回文字符串字典序小于原字符串
20.         ans = t
21.     else:
22.         # 如果直接构造的回文不满足字典序小于 s 的条件
23.         # 从回文中心开始尝试减小字典序
24.         i = (n - 1) >> 1  # 确定中间位置，向左遍历
25.         while i >= 0:
26.             if s[i] == 'a':  # 如果当前字符为 'a'
27.                 s[i] = 'z'  # 将其变为 'z'
28.             else:
29.                 s[i] = chr(ord(s[i]) - 1)  # 将当前字符减小一个字母
30.                 break  # 减小成功后退出循环
31.             i -= 1  # 向左移动指针
32.         if i == -1:  # 如果遍历完成仍无法减小字典序
33.             ans = ["-1"]  # 无法构造符合条件的字符串
34.         else:
35.             # 成功减小字典序后，重新构造回文
36.             ans = build(s)
37.     return "".join(ans)  # 返回最终结果，将列表转为字符串
39. # 测试用例
40. if __name__ == '__main__':
41.     # 测试样例1，输入 "abc"，期望输出 "aba"
42.     print(solution(s = "abc") == 'aba')  # 输出 True 表示通过测试
43.     # 测试样例2，输入 "cba"，期望输出 "cac"
44.     print(solution(s = "cba") == 'cac')  # 输出 True 表示通过测试
45.     # 测试样例3，输入 "aaa"，期望输出 "-1"
46.     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，得到中央索引位置。
    
  • 这是一个向左偏的中央索引，实用于在字符串中以双指针的方式从中央向两边遍历。
    
  
  

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。