网站建设德语番禺软件公司

题目链接LeetCode1328

1.题目

给你一个由小写英文字母组成的回文字符串 palindrome ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小 ，且 不是 回文串。
请你返回结果字符串。如果无法做到，则返回一个 空串 。
如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，"abcc” 字典序比 “abcd” 小，因为不同的第一个位置是在第四个字符，显然 ‘c’ 比 ‘d’ 小。

2.示例

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

2）示例 2：
输入：palindrome = “a”
输出：“”
解释：不存在替换一个字符使 “a” 变成非回文的方法，所以返回空字符串。

3）提示：

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

3.分析

关于让字符串字典序最小，首先的思路是，我们从头到尾扫一遍字符串，看看把它的字符换小可不可以满足不是回文串的需求，如果可以，返回修改后的字符串。如果前者都不能满足需求，我们可以从尾到头扫一遍字符串，把它的字符换大看可不可以满足不是回文串的需求。如果都不能满足，那么返回“”。

4.代码

class Solution {
public:bool check(string s){int left=0,right=s.size()-1;while(left+1<=right){if(s[left]!=s[right]) return false;//不是回文串left++;right--;}return true;}string breakPalindrome(string palindrome) {bool flag=false;for(int i=0;i<palindrome.size();i++)for(char j='a';j<palindrome[i];j++){string test=palindrome.substr(0,i)+j+palindrome.substr(i+1,palindrome.size()-i-1);// if(i==2&&j=='a') return test;if(!check(test)) return test;}for(int i=palindrome.size()-1;i>=0;i--)for(char j=palindrome[i]+1;j<='z';j++){string test=palindrome.substr(0,i)+j+palindrome.substr(i+1,palindrome.size()-i-1);if(!check(test)) return test;}return "";}
};