当前位置：首页 > news >正文

LeetCode 1328.破坏回文串：贪心

news 2025/8/27 0:39:04

【LetMeFly】1328.破坏回文串：贪心

力扣题目链接：https://leetcode.cn/problems/break-a-palindrome/

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

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

如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，"abcc” 字典序比 "abcd" 小，因为不同的第一个位置是在第四个字符，显然 'c' 比 'd' 小。

示例 1：

输入：palindrome = "abccba"
输出："aaccba"
解释：存在多种方法可以使 "abccba" 不是回文，例如 "zbccba", "aaccba", 和 "abacba" 。
在所有方法中，"aaccba" 的字典序最小。

示例 2：

输入：palindrome = "a"
输出：""
解释：不存在替换一个字符使 "a" 变成非回文的方法，所以返回空字符串。

提示：

1 <= palindrome.length <= 1000
palindrome 只包含小写英文字母。

解题方法：贪心

如果字符串只有一个字符，那么改成什么都是回文，直接返回空字符串。

如果字符串的长度为奇数，那么修改正中间的字符是没有意义的，修改后仍是回文串。

为了让修改后的字符串前面字符尽可能小，对于一个长度不只为1的字符串：

遍历字符串的前一半（不遍历到字符串正中间元素或后半字符串），一旦出现非a字符，就将这个字符修改为a并返回
否则（前半字符串(不包含正中间字符)全是a）说明后半字符串也全是a，将最后一个字符修改为b并返回
时间复杂度 $O (l e n (p a l in d ro m e))$
空间复杂度 $O (1)$ 。C++可变字符串可直接修改原字符串并返回；其他不可变字符串的编程语言返回值不计入算法空间复杂度。

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-03-05 12:55:06* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-05 12:56:14*/
class Solution {
public:string breakPalindrome(string palindrome) {if (palindrome.size() == 1) {return "";}for (int i = 0; i < palindrome.size() / 2; i++) {if (palindrome[i] != 'a') {palindrome[i] = 'a';return palindrome;}}palindrome.back() = 'b';return palindrome;}
};

Python

'''
Author: LetMeFly
Date: 2025-03-05 15:57:15
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-05 15:59:07
'''
class Solution:def breakPalindrome(self, palindrome: str) -> str:if len(palindrome) == 1:return ''s = list(palindrome)for i in range(len(palindrome) // 2):if palindrome[i] != 'a':s[i] = 'a'return ''.join(s)s[-1] = 'b'return ''.join(s)

Java

/** @Author: LetMeFly* @Date: 2025-03-05 16:00:14* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-05 16:02:39*/
class Solution {public String breakPalindrome(String palindrome) {if (palindrome.length() == 1) {return new String();}char[] s = palindrome.toCharArray();for (int i = 0; i < s.length / 2; i++) {if (s[i] != 'a') {s[i] = 'a';return new String(s);}}s[s.length - 1] = 'b';return new String(s);}
}

Go

/** @Author: LetMeFly* @Date: 2025-03-05 16:05:35* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-05 16:07:53*/
package mainfunc breakPalindrome(palindrome string) string {if len(palindrome) == 1 {return ""}for i := 0; i < len(palindrome) / 2; i++ {if palindrome[i] != 'a' {return palindrome[:i] + "a" + palindrome[i + 1:]}}return palindrome[:len(palindrome) - 1] + "b"
}