leetcode
leetcode 1101 ~ 1150
破坏回文串

破坏回文串

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 16.0 MB


/*
 * 思路:
 * 1. 使用 IntStream 来遍历字符串的前半部分,找到第一个不是 'a' 的字符,替换为 'a'。
 * 2. 如果前半部分都是 'a',则将最后一个字符替换为 'b'。
 * 3. 如果字符串长度为 1,则无法替换一个字符使其非回文,返回空字符串。
 */
import java.util.stream.IntStream;
public class Solution {
    public String breakPalindrome(String palindrome) {
        if (palindrome.length() == 1) return ""; // 单字符无法变成非回文
        StringBuilder sb = new StringBuilder(palindrome);
        IntStream.range(0, sb.length() / 2).filter(i -> sb.charAt(i) != 'a').findFirst().ifPresent(i -> sb.setCharAt(i, 'a'));
        if (palindrome.equals(sb.toString())) sb.setCharAt(sb.length() - 1, 'b');
        return sb.toString();
    }
}

解释

方法:

此题解的核心思路是通过尽量少的改动使回文字符串不再是回文的同时字典序最小。首先,检查字符串长度,如果是1,则无法通过改变一个字符使其不是回文,直接返回空字符串。接着,遍历字符串的前半部分,寻找第一个不是'a'的字符,将其替换为'a',因为'a'是最小的字母,这样可以保证得到的新字符串字典序尽可能小。如果前半部分所有字符都是'a',则将最后一个字符改为'b',因为整个字符串替换'a'后仍是回文,所以改变最后一个字符可以确保字符串不是回文,而改为'b'能保持字典序较小。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么选择替换第一个不是'a'的字符为'a',而不是选择其他字母进行替换,这样做的依据是什么?
在破坏回文串的过程中,目的是使字符串不再是回文的同时,保证字典序尽可能小。字母'a'是所有字母中字典序最小的,因此,将非'a'的字符替换为'a'可以使得修改后的字符串的字典序比替换成其他任何字母都要小。此外,从字符串的前半部分开始寻找第一个非'a'的字符进行替换,可以确保在不影响回文性质的前提下,尽可能减小字典序。
🦆
如果输入的回文串已经是全'a'的情况下,为什么将最后一个字符改为'b'能保证结果字符串不是回文,这种选择是基于什么原理?
如果一个回文串完全由字符'a'组成,那么不论修改任何一个'a'为其他字符,新生成的字符串都将不再是回文串。选择将最后一个字符'a'改为'b'而不是改变其他位置的'a',是因为这样可以保持字典序最小('a'本身就是最小的,只改最后一个'a'为'b'才能最小幅度增加字典序)。此外,由于回文串的对称性,最后一个字符在回文中通常与第一个字符相对应,改变它能有效地破坏回文结构。
🦆
在题解中提到,如果字符串长度为1,则返回空字符串。能否详细解释为什么长度为1的回文字符串不能通过改变一个字符来不再是回文?
长度为1的字符串由单一字符构成,无论这个字符是什么,它总是回文,因为正序和倒序都是相同的(仅一个字符)。在这种情况下,改变这唯一的字符只会将它变成另一个字符,但该字符串仍然是回文(因为它仍然只包含一个相同的字符)。因此,不能通过改变单个字符使长度为1的字符串不再是回文。
🦆
题解中提到遍历字符串的前半部分,这种策略是否在所有情况下都是最优的,是否有可能存在更优的遍历或修改策略?
遍历字符串的前半部分是基于回文的对称性质。由于回文字符串的后半部分是前半部分的镜像,只需考虑前半部分即可找到破坏回文所需的最小改动点。这种策略在保证最小字典序的同时,减少了需要检查的字符数量,是一种高效的策略。在大多数情况下,这是最优的策略,因为它直接关注于破坏回文的关键点,即对称的中心。但如果有特殊要求,例如最小化改动的字母数或改动的位置,则可能需要考虑其他策略。

相关问题