Leetcode 1328:破坏回文串(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1328:破坏回文串(超详细的解法!!!)

in leetcode with 0 comment

给你一个回文字符串 palindrome ,请你将其中 一个 字符用任意小写英文字母替换,使得结果字符串的字典序最小,且 不是 回文串。

请你返回结果字符串。如果无法做到,则返回一个空串。

示例 1:

输入:palindrome = "abccba"
输出:"aaccba"

示例 2:

输入:palindrome = "a"
输出:""

提示:

解题思路

首先不难想到暴力解法,就是遍历palindrome的字母替换成其他26个字母中的任意一个,替换后如果不是回文字符串的话将其添加到结果数组中去。

class Solution:
    def breakPalindrome(self, p: str) -> str:
        res = []
        for i in range(len(p)):
            for c in string.ascii_lowercase:
                s = p[:i]+c+p[i+1:]
                if s != s[::-1]:
                    res.append(s)
        return sorted(res)[0] if res else ""

实际上可以更加简洁,我们可以使用贪心处理该问题。

首先给定字符串是回文串,那么必然左右对称,所以我们只需要思考字符串的左半边即可。要想字典序最小,那么最好的办法就是将左边第一个不为'a'的字符替换为'a'。存在两个边界:

class Solution:
    def breakPalindrome(self, p: str) -> str:
        for i in range(len(p) // 2):
            if p[i] != 'a':
                return p[:i] + 'a' + p[i + 1:]
        return p[:-1] + 'b' if p[:-1] else ''

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses