05 August 2008
给一个由小写英文字母组成的回文字符串 palindrome ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小 ，且 不是 回文串。
请返回结果字符串。如果无法做到，则返回一个 空串 。
如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，”abcc” 字典序比 “abcd” 小，因为不同的第一个位置是在第四个字符，显然 ‘c’ 比 ‘d’ 小。
示例 1：
1
2
3
4
输入：palindrome = "abccba"
输出："aaccba"
解释：存在多种方法可以使 "abccba" 不是回文，例如 "zbccba", "aaccba", 和 "abacba" 。
在所有方法中，"aaccba" 的字典序最小。
示例 2：
1
2
3
输入：palindrome = "a"
输出：""
解释：不存在替换一个字符使 "a" 变成非回文的方法，所以返回空字符串。
示例 3：
1
2
输入：palindrome = "aa"
输出："ab"
示例 4：
1
2
输入：palindrome = "aba"
输出："abb"
贪心的思想：
1.因为是回文串，根据要求，只需要关注前 n/2 个字符
2.因为需要字典序最小，所以从左端开始判断如果不是a，就改为a此时必然符合要求直接返回
3.如果前面没有返回，说明前面字符串里全是a，那么由回文串知道后面的部分也全是a
4.此时字典序最小的情况就是把最后一个位置改为b直接返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public String breakPalindrome(String palindrome) {
int len = palindrome.length();
if (len == 1) {
return "";
}
StringBuilder sb = new StringBuilder(palindrome);
for (int i = 0; i < len / 2; i++) {
if (sb.charAt(i) != 'a') {
sb.setCharAt(i, 'a');
return sb.toString();
}
}
sb.setCharAt(len - 1, 'b');
return sb.toString();
}
}