LEETCODE 1328. Break a Palindrome 解题思路分析

题目大意：

破坏回文串

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

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

示例 1：

输入：palindrome = "abccba"
输出："aaccba"

示例 2：

输入：palindrome = "a"
输出：""

提示：

• 1 <= palindrome.length <= 1000
• palindrome 只包含小写英文字母。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1328

解题思路分析：

本题需要考虑到几种情况：

1. 如果字符串长度为1，那么我们无论怎么修改最终都是回文，此时返回空。
2. 理论上，我们需要将尽量靠前的字符修改成a，这样可以保证其字典顺序最小。但是如果靠前的字符已经是a，那么我们只能继续向后寻找首个不是a的字符，但是该字符位置不能是字符串的正中央，否则，修改后还是回文。
3. 如果字符串所有字符均是a，那么应该将最后一位修改成b，这样可以保证字典顺序最小。

实现代码：

public String breakPalindrome(String palindrome) {
    // 如果字符串长度小于等于1，返回空
    if(palindrome.length()<=1) return "";
    // 为了方便操作字符串，将其转为StringBuilder
    StringBuilder sb = new StringBuilder(palindrome);
    // 从头循环每一个字符
    for(int i=0;i<sb.length();i++){
        // 如果当前字符不是a，并且位置不在字符串正中
        if(sb.charAt(i)!='a'&&i!=sb.length()-1-i){
            // 将其修改为a并返回
            sb.setCharAt(i,'a');
            return sb.toString();
        }
        // 如果到字符串结尾仍未找到a以外的字符（除了正中央）
        if(i==sb.length()-1){
            // 将最后一位修改为b并返回
            sb.setCharAt(i,'b');
            return sb.toString();
        }
    }
    return "";
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Break a Palindrome.

Memory Usage: 37.6 MB, less than 100.00% of Java online submissions for Break a Palindrome.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1328-break-a-palindrome-解题思路分析/