X

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.

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