leetcode 1328.破坏回文串

题目链接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 "";
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25