目录

1328:破坏回文串(1473 分)

力扣第 18 场双周赛第 2 题

题目

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

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

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

示例 1:

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

示例 2:

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

提示:

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

分析

  • 假如长度 1,显然无法做到,返回空
  • 要使字典序最小,考虑尽可能前面的某位变为 ‘a’
  • 因此遍历前半部分(不包括中心位置),找到第一个不为 ‘a’ 的位置,变为 ‘a’ 即可
  • 如果全为 ‘a’,那么将最后一位变为 ‘b’ 即可

解答

1
2
3
4
5
6
7
8
9
def breakPalindrome(self, palindrome: str) -> str:
	s = palindrome
	n = len(s)
	if n==1:
		return ''
	for i in range(n//2):
		if s[i] != 'a':
			return s[:i]+'a'+s[i+1:]
	return s[:-1]+'b'

36 ms