给你一个回文字符串
palindrome
，请你将其中
一个
字符用任意小写英文字母替换，使得结果字符串的字典序最小，且
不是
回文串。
请你返回结果字符串。如果无法做到，则返回一个空串。
示例 1：
输入：palindrome = "abccba"
输出："aaccba"
示例 2：
输入：palindrome = "a"
输出：""
提示：
-
1 <= palindrome.length <= 1000
-
palindrome
只包含小写英文字母。
思路：
首先先明确如果只有一个字母，那么无解。
其次思考一下general的情况，对于输入比如 “abdba”，我们应该把第一个比a大的字母变为a，这样可以使得到的新字符串最小而且不是回文字符串，
但同时又要考虑一些 edge case，
1. 如果全部是a怎么办？答：应该把最后一个字母变成b，
2. 如果第一个比a大的字母变成a之后，数组依然回文怎么办？比如输入：”aba”， 按照上面的方法得到的答案”aaa”依然回文。
答：还是把最后一个字母变成b
时间复杂度：O（N）
空间复杂度：O（N）
class Solution(object):
def breakPalindrome(self, palindrome):
"""
:type palindrome: str
:rtype: str
"""
if len(palindrome) == 1:
return ""
if len(set(palindrome)) == 1:
if palindrome[0] == "a":
return palindrome[:-1] + "b"
for ch in palindrome:
if ord(ch) > ord("a"):
res = palindrome.replace(ch, "a", 1)
return res if res != res[::-1] else palindrome[:-1] + "b"
版权声明：本文为qq_32424059原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。