返回介绍

solution / 1300-1399 / 1328.Break a Palindrome / README

发布于 2024-06-17 01:03:20 字数 3614 浏览 0 评论 0 收藏 0

1328. 破坏回文串

English Version

题目描述

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

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

如果两个字符串长度相同,那么字符串 a 字典序比字符串 b 小可以这样定义:在 ab 出现不同的第一个位置上,字符串 a 中的字符严格小于 b 中的对应字符。例如,"abcc” 字典序比 "abcd" 小,因为不同的第一个位置是在第四个字符,显然 'c''d' 小。

 

示例 1:

输入:palindrome = "abccba"
输出:"aaccba"
解释:存在多种方法可以使 "abccba" 不是回文,例如 "_z_bccba", "a_a_ccba", 和 "ab_a_cba" 。
在所有方法中,"aaccba" 的字典序最小。

示例 2:

输入:palindrome = "a"
输出:""
解释:不存在替换一个字符使 "a" 变成非回文的方法,所以返回空字符串。

 

提示:

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

解法

方法一:贪心

我们先判断字符串的长度是否为 $1$,若是则直接返回空串。

否则,我们从左到右遍历字符串的前半部分,找到第一个不为 'a' 的字符,将其改为 'a' 即可。如果不存在这样的字符,那么我们将最后一个字符改为 'b' 即可。

时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为字符串的长度。

class Solution:
  def breakPalindrome(self, palindrome: str) -> str:
    n = len(palindrome)
    if n == 1:
      return ""
    s = list(palindrome)
    i = 0
    while i < n // 2 and s[i] == "a":
      i += 1
    if i == n // 2:
      s[-1] = "b"
    else:
      s[i] = "a"
    return "".join(s)
class Solution {
  public String breakPalindrome(String palindrome) {
    int n = palindrome.length();
    if (n == 1) {
      return "";
    }
    char[] cs = palindrome.toCharArray();
    int i = 0;
    while (i < n / 2 && cs[i] == 'a') {
      ++i;
    }
    if (i == n / 2) {
      cs[n - 1] = 'b';
    } else {
      cs[i] = 'a';
    }
    return String.valueOf(cs);
  }
}
class Solution {
public:
  string breakPalindrome(string palindrome) {
    int n = palindrome.size();
    if (n == 1) {
      return "";
    }
    int i = 0;
    while (i < n / 2 && palindrome[i] == 'a') {
      ++i;
    }
    if (i == n / 2) {
      palindrome[n - 1] = 'b';
    } else {
      palindrome[i] = 'a';
    }
    return palindrome;
  }
};
func breakPalindrome(palindrome string) string {
  n := len(palindrome)
  if n == 1 {
    return ""
  }
  i := 0
  s := []byte(palindrome)
  for i < n/2 && s[i] == 'a' {
    i++
  }
  if i == n/2 {
    s[n-1] = 'b'
  } else {
    s[i] = 'a'
  }
  return string(s)
}
function breakPalindrome(palindrome: string): string {
  const n = palindrome.length;
  if (n === 1) {
    return '';
  }
  const s = palindrome.split('');
  let i = 0;
  while (i < n >> 1 && s[i] === 'a') {
    i++;
  }
  if (i == n >> 1) {
    s[n - 1] = 'b';
  } else {
    s[i] = 'a';
  }
  return s.join('');
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文