class Solution {
public:
string breakPalindrome(string palindrome) {
}
};
1328. 破坏回文串
给你一个由小写英文字母组成的回文字符串 palindrome ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小 ，且 不是 回文串。
请你返回结果字符串。如果无法做到，则返回一个 空串 。
如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，"abcc” 字典序比 "abcd" 小，因为不同的第一个位置是在第四个字符，显然 'c' 比 'd' 小。
示例 1：
输入：palindrome = "abccba" 输出："aaccba" 解释：存在多种方法可以使 "abccba" 不是回文，例如 "zbccba", "aaccba", 和 "abacba" 。 在所有方法中，"aaccba" 的字典序最小。
示例 2：
输入：palindrome = "a" 输出："" 解释：不存在替换一个字符使 "a" 变成非回文的方法，所以返回空字符串。
提示：
1 <= palindrome.length <= 1000palindrome 只包含小写英文字母。原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-23 11:38:23
func breakPalindrome(palindrome string) string {
if len(palindrome) == 1 {
return ""
}
for i, c := range palindrome {
smaller := getSmallerChar(c)
if len(smaller) > 0 {
if i == len(palindrome) / 2 && len(palindrome) % 2 != 0 {
continue
}
return palindrome[:i] + smaller + palindrome[i+1:]
}
}
i := len(palindrome) - 1
bigger := getBiggerChar(rune(palindrome[i]))
if len(bigger) == 0 {
return ""
}
return palindrome[:i] + bigger
}
func getSmallerChar(c rune) string {
if 'a' < c {
return "a"
} else if 'a' == c {
return ""
}
return ""
}
func getBiggerChar(c rune) string {
if 'z' > c {
return string(c + 1)
} else if 'z' == c {
return ""
}
return ""
}
python3 解法, 执行用时: 48 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-23 11:37:35
class Solution:
def breakPalindrome(self, palindrome: str) -> str:
if len(palindrome) == 1:
return ''
s = list(palindrome)
n, flag = len(s), False
for i in range(n):
if s[i] != 'a' and (n % 2 == 0 or n % 2 != 0 and i != n // 2):
s[i] = 'a'
flag = True
break
if not flag:
s[-1] = 'b'
return ''.join(s)
python3 解法, 执行用时: 40 ms, 内存消耗: 16 MB, 提交时间: 2023-09-23 11:37:22
class Solution:
def breakPalindrome(self, palindrome: str) -> str:
str_len = len(palindrome)
if str_len < 2:
return ""
for idx in range(str_len >> 1):
if palindrome[idx] > 'a':
return palindrome[:idx] + 'a' + palindrome[idx+1:]
return palindrome[:str_len-1] + 'b'
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.5 MB, 提交时间: 2023-09-23 11:36:56
class Solution {
public:
string breakPalindrome(string palindrome) {
size_t len = palindrome.size(), half = (len - 2) >> 1;
if(len < 2) return "";
for (size_t i = 0; i <= half; ++i)
if (palindrome[i] > 'a') {
palindrome[i] = 'a';
return palindrome;
}
palindrome[len - 1] = 'b';
return palindrome;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 39.3 MB, 提交时间: 2023-09-23 11:36:40
class Solution {
public String breakPalindrome(String palindrome) {
int len = palindrome.length(), half = (len - 2) >> 1;
if (len < 2) return "";
char[] ch_arr = palindrome.toCharArray();
for (int i = 0; i <= half; ++i)
if (ch_arr[i] > 'a') {
ch_arr[i] = 'a';
return String.valueOf(ch_arr);
}
ch_arr[len - 1] = 'b';
return String.valueOf(ch_arr);
}
}