文章

[LeetCode] 每日一题 1328. 破坏回文串

题目链接

https://leetcode.cn/problems/break-a-palindrome

题目描述

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

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

如果两个字符串长度相同,那么字符串 a 字典序比字符串 b 小可以这样定义:在 ab 出现不同的第一个位置上,字符串 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. 回文串的特点

    • 由于字符串是回文,对称结构使得左右两边的字符相同

    • 要想让它变成非回文,我们只需改变其中一个字符

  2. 贪心策略

    • 尽量让字典序最小:优先将左半部分的非 'a' 变为 'a',这样可以最小化影响

    • 特殊情况:如果整个字符串都是 'a',那么将最后一个字符改成 'b',保证非回文,同时字典序尽可能小

  3. 边界情况

    • 长度为 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'

与昨天的题目相比,这道题更像是一道思维题,一旦想通了核心逻辑,代码实现非常简单

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0