[LeetCode] 每日一题 1328. 破坏回文串
题目链接
题目描述
给你一个由小写英文字母组成的回文字符串 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
只包含小写英文字母。
解题思路
本题的核心在于最小字典序和破坏回文结构,其实是一个简单的贪心问题,属于脑筋急转弯类型
回文串的特点
由于字符串是回文,对称结构使得左右两边的字符相同
要想让它变成非回文,我们只需改变其中一个字符
贪心策略
尽量让字典序最小:优先将左半部分的非
'a'
变为'a'
,这样可以最小化影响特殊情况:如果整个字符串都是
'a'
,那么将最后一个字符改成'b'
,保证非回文,同时字典序尽可能小
边界情况
长度为
1
的回文串无法修改为非回文,直接返回""
代码实现
class Solution {
public String breakPalindrome(String palindrome) {
int n = palindrome.length();
if (n <= 1) {
return "";
}
char[] s = palindrome.toCharArray();
for (int i = 0; i * 2 + 1 < n; i++) {
if (s[i] != 'a') {
s[i] = 'a';
return new String(s);
}
}
s[n - 1] = 'b';
return new String(s);
}
}
复杂度分析
时间复杂度:只需遍历字符串的一半,即
O(n/2)
,最终仍为 O(n)空间复杂度:只使用了一个字符数组
s
,开销为 O(n)(但可以直接修改char[]
,避免额外存储)
总结
这道题的关键在于理解回文的对称性,并利用贪心策略快速找到最优解:
尽量让字典序最小,优先修改前半部分的非
'a'
为'a'
特殊情况处理,如果字符串全是
'a'
,改最后一个字符为'b'
与昨天的题目相比,这道题更像是一道思维题,一旦想通了核心逻辑,代码实现非常简单
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。