难度: Hard
Submission
运行时间: 31 ms
内存: 17.8 MB
class Solution(object):
def nextPalindrome(self, num):
n = len(num)
st = []
start_index = -1
for i in range(n // 2 - 1, -1, -1):
if st and num[i] < st[-1][0]:
start_index = i
while st and num[i] < st[-1][0]:
_, end_index = st.pop()
break
st.append([num[i], i])
if start_index == -1:
return ''
else:
s = num[: start_index] + num[end_index] + num[n // 2 - 1: end_index: -1] + num[start_index] + num[end_index - 1: start_index: -1]
if n % 2:
return s + num[n // 2] + s[::-1]
else:
return s + s[::-1]
Explain
该题目的目的是找到由相同数字组成的下一个回文串。算法的主要思路是从中心向外寻找可以形成下一个较大的回文串的机会。具体步骤如下： 1. 使用一个栈来存储遍历过的字符和它们的索引，以便在找到一个更小的字符时可以进行替换。 2. 从字符串的中心位置向左遍历，寻找第一个可以交换的位置，这个位置的字符应该小于其对应的栈顶字符。 3. 一旦找到这样的位置，从栈中移除所有比当前字符大的元素，记录下可以交换的位置。 4. 如果没有找到合适的交换位置，则返回空字符串。 5. 根据找到的交换位置，构造新的回文串，确保新串比原串大。 6. 特别注意处理字符串长度为奇数的情况，中间的字符需要保持不变。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution(object):
def nextPalindrome(self, num):
n = len(num) # 获取字符串长度
st = [] # 初始化栈
start_index = -1 # 初始化可以开始交换的位置
# 从中点向左遍历
for i in range(n // 2 - 1, -1, -1):
if st and num[i] < st[-1][0]:
start_index = i # 找到可以交换的位置
while st and num[i] < st[-1][0]:
_, end_index = st.pop() # 移除栈顶元素直到找到更小的字符
break
st.append([num[i], i]) # 将当前字符和索引压入栈中
if start_index == -1:
return '' # 如果没有交换位置，返回空串
else:
s = num[: start_index] + num[end_index] + num[n // 2 - 1: end_index: -1] + num[start_index] + num[end_index - 1: start_index: -1] # 构造新的回文串
if n % 2:
return s + num[n // 2] + s[::-1] # 如果是奇数长度，处理中间字符
else:
return s + s[::-1] # 返回构造的回文串
Explore
在这个算法中，栈用于存储遍历过的字符及其索引，这样做的目的是为了回溯和比较。当从中心向左遍历时，我们希望找到一个较小的字符，使其与之前遍历过的较大字符交换位置。栈的后进先出特性允许我们访问最近添加的元素，这是比较当前元素与之前元素大小的理想结构。使用栈可以方便地找到第一个可以进行交换的位置，即第一个大于当前遍历字符的栈顶字符，这样的交换有助于构造一个更大的回文串。
当我们找到一个比栈顶元素小的字符时，需要移除所有比当前字符大的栈顶元素，以便找到最小的且能使结果回文串更大的交换位置。这样做的目的是确保交换后构成的新回文串尽可能小（在确保比原回文串大的前提下），从而保证这是下一个更大的回文串。如果保留了一个过大的字符在栈中，可能会导致交换后的新串不是最接近原串的下一个回文串。
新的回文串是通过找到的可交换位置构造的，确保新串比原串大的关键在于选择正确的交换位置和交换方式。首先，通过栈找到一个当前字符小于的字符，进行交换，这可以确保在保持回文结构的同时，左半部分的一个较小字符被替换为一个较大的字符，从而使整个串变大。然后，利用回文的对称性，将交换后的左半部分以逆序的形式复制到右半部分，确保整体上新串大于原串。
当字符串长度为奇数时，中间的字符处于对称轴上，不参与左右交换。因此，在构造新的回文串时，这个中间字符需要保持不变。这是因为改变中间字符可能会破坏回文结构，或者导致不必要的复杂性增加。保持中间字符不变有助于保证回文的对称性，同时简化构造过程。