难度: Medium
Submission
运行时间: 35 ms
内存: 16.1 MB
class Solution:
def makePalindrome(self, s: str) -> bool:
times = 2
for i in range(len(s)//2):
if s[i] != s[len(s)-1-i]:
times -= 1
if times < 0:
return False
return True
Explain
此题的目标是判断给定字符串是否可以通过至多两次修改变成回文串。解题思路是通过一次遍历的方式，从字符串的两头向中心检查字符是否相等。如果发现不相等的字符，允许减少一次修改机会（即times变量减1）。如果在遍历过程中，需要的修改次数超过2次（times变成负数），则直接返回False。如果整个遍历完成后，修改次数没有超过2次，返回True。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def makePalindrome(self, s: str) -> bool:
times = 2 # 允许的最大修改次数
for i in range(len(s)//2): # 只需检查到字符串的一半
if s[i] != s[len(s)-1-i]: # 检查两端字符是否相等
times -= 1 # 不相等则减少一次修改机会
if times < 0: # 如果修改次数用完
return False # 不能变成回文串
return True # 修改次数足够，可以变成回文串
Explore
从字符串两端向中心遍历是因为回文串具有中心对称的特性。这种方式可以直接比较首尾字符，如果不相等，则可立即知道需要修改。而从中心向两端遍历则需先确定中心位置，对于偶数长度的字符串，这不是一个明确的单个字符，处理起来更复杂。从两端向中心遍历更直接有效地利用了回文的对称性质。
减少修改次数的逻辑是为了简化判断过程。在实际操作中，减少一次修改次数实际上隐含了进行了一次字符替换的假设，即将一个字符替换成另一个以匹配对称位置的字符。这种假设是在不实际修改字符串的情况下，快速判断能否通过有限次修改达成回文串的有效方法。
times变量初始化为2表示最多允许进行两次修改操作，以使字符串变为回文串。这里的修改操作通常指的是替换操作，即将一个字符换成另一个字符。虽然理论上可以考虑删除或添加字符的操作，但在本题的上下文中，主要考虑的是替换操作，因为这是最直接处理字符不匹配的方式。
在长度为奇数的字符串中，中间的字符实际上没有对应的字符与之对称，因此在从两端向中心遍历的过程中不需要检查中间的字符。中间的字符不影响回文的判断，因为它总是自己与自己对称。因此，算法只检查到字符串的一半，不包括中间字符（如果存在）。