破坏回文串
难度:
标签:
题目描述
代码结果
运行时间: 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'的情况下,为什么将最后一个字符改为'b'能保证结果字符串不是回文,这种选择是基于什么原理?
▷🦆
在题解中提到,如果字符串长度为1,则返回空字符串。能否详细解释为什么长度为1的回文字符串不能通过改变一个字符来不再是回文?
▷🦆
题解中提到遍历字符串的前半部分,这种策略是否在所有情况下都是最优的,是否有可能存在更优的遍历或修改策略?
▷