【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 <= 1000palindrome 只包含小写英文字母。
解题方法：贪心
如果字符串只有一个字符，那么改成什么都是回文，直接返回空字符串。
如果字符串的长度为奇数，那么修改正中间的字符是没有意义的，修改后仍是回文串。
为了让修改后的字符串前面字符尽可能小，对于一个长度不只为1的字符串：
遍历字符串的前一半（不遍历到字符串正中间元素或后半字符串），一旦出现非a字符，就将这个字符修改为a并返回
否则（前半字符串(不包含正中间字符)全是a）说明后半字符串也全是a，将最后一个字符修改为b并返回
时间复杂度$O(len(palindrome))$
空间复杂度$O(1)$。C++可变字符串可直接修改原字符串并返回；其他不可变字符串的编程语言返回值不计入算法空间复杂度。
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| '''
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
package main
func 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"
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源