难度: Hard
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1：
输入：s = "aacecaaa" 输出："aaacecaaa"
示例 2：
输入：s = "abcd" 输出："dcbabcd"
提示：
0 <= s.length <= 5 * 104s仅由小写英文字母组成
Submission
运行时间: 41 ms
内存: 16.2 MB
class Solution:
def shortestPalindrome(self, s: str) -> str:
s1 = s[::-1]
if s == s1:
return s
n = len(s)
a, b, i = 1, n // 2, 0
while b:
while a <= b:
c = a + b >> 1
j = s1.find(s[:c], i)
if j < 0 or j > n - c * 2:
b = c - 1
i = max(i, n - c * 2 + 1)
continue
m = n - j >> 1
if s1[j + c:j + m] == s[c:m]:
return s1[:j] + s
i = j + 1
a = c
a = 1
return s1[:-1] + s
Explain
这个题解采用了二分查找的思路。首先将原字符串 s 翻转得到 s1。如果 s 本身就是回文串，直接返回 s。否则，通过二分查找的方式，在 s1 中查找 s 的前缀，找到最长的能够形成回文串的前缀。查找过程中，使用双指针 a 和 b 分别指向查找范围的起始和结束位置，每次取中点 c，判断 s1 中是否存在 s[:c] 子串。如果存在，则判断 s1[j+c:j+m] 与 s[c:m] 是否相等（其中 j 为 s[:c] 在 s1 中的起始位置，m 为 s[:c] 的中点），如果相等则找到了最长的回文前缀，返回 s1[:j] + s。如果不相等，则将查找范围缩小到 [c, b]。如果 s[:c] 在 s1 中不存在，则将查找范围缩小到 [a, c-1]。最后，如果没有找到任何回文前缀，则返回 s1[:-1] + s。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def shortestPalindrome(self, s: str) -> str:
s1 = s[::-1] # 将字符串 s 翻转得到 s1
if s == s1: # 如果 s 本身是回文串，直接返回 s
return s
n = len(s) # 字符串长度
a, b, i = 1, n // 2, 0 # 二分查找的起始位置 a，结束位置 b，查找起始位置 i
while b:
while a <= b:
c = a + b >> 1 # 二分查找的中点 c
j = s1.find(s[:c], i) # 在 s1 中查找 s[:c] 子串的起始位置 j
if j < 0 or j > n - c * 2: # 如果 s[:c] 在 s1 中不存在或者位置不合法
b = c - 1 # 将查找范围缩小到 [a, c-1]
i = max(i, n - c * 2 + 1) # 更新查找起始位置 i
continue
m = n - j >> 1 # s[:c] 的中点位置 m
if s1[j + c:j + m] == s[c:m]: # 判断 s1[j+c:j+m] 与 s[c:m] 是否相等
return s1[:j] + s # 如果相等，找到了最长的回文前缀，返回结果
i = j + 1 # 如果不相等，将查找起始位置更新为 j+1
a = c # 将查找范围缩小到 [c, b]
a = 1 # 如果当前查找范围没有找到回文前缀，将 a 重置为 1，继续查找
return s1[:-1] + s # 如果没有找到任何回文前缀，返回 s1[:-1] + s
Explore
将原字符串 s 翻转得到 s1 主要是为了方便查找和确认 s 的前缀是否能与 s1 的后缀匹配，从而构成回文。回文的特性是前后对称，所以通过比较原字符串的前缀与翻转字符串的后缀（实际上在翻转字符串中的位置相当于前缀），可以有效地判定最长的回文前缀。这种方法简化了判断过程，避免了复杂的回文判断操作，提高了效率。
查找区间 [a, b] 的初始值是基于最坏情况的考虑，即寻找直到中点的前缀以检查其中可能的最长回文前缀。初始值设置为从 1 到 n//2 主要是因为回文前缀的长度至少为 1 且最长不会超过字符串长度的一半。查找区间的调整逻辑是基于二分查找的原理，每次根据中点 c 的判断结果来缩小查找范围，如果 s[:c] 在 s1 中位置不合法或不存在，说明当前 c 作为回文前缀的可能性较小，因此调整查找范围到 [a, c-1]。
当 s1.find(s[:c]) 返回 -1 时，这意味着 s[:c] 这个前缀在 s1 中没有找到匹配的子串，即 s1 中不存在以该前缀结束的子串。因此，任何长于 c 的前缀也不可能在 s1 中找到匹配的子串。所以，为了找到可能存在的最长回文前缀，我们需要缩短前缀长度，即将查找范围调整到 [a, c-1]，继续在更短的前缀中寻找匹配。
在这部分的逻辑中，s1[j+c:j+m] 与 s[c:m] 的比较是为了确认在找到 s[:c] 在 s1 中的匹配后，这个匹配是否能扩展到更长的回文。具体来说，j 是 s[:c] 在 s1 中的起始位置，c 是当前考虑的前缀长度，m 是 s1 中匹配的结束位置的中点。这个比较确认从 j+c 到 j+m 的子串是否与 s 从 c 到 m 的子串相等，如果相等，说明 s 的起始部分到 m 可以和 s1 的相应部分形成回文，因此这部分 s 加上 s1 的前 j 个字符（即 s1 中与 s 前缀相匹配的部分之前的字符）构成了所求的最短回文串。