LeetCode 每日一题 1328. 破坏回文串

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 <= 1000
palindrome 只包含小写英文字母。

题解

题目很好理解，我们需要改变回文字符串中的一个字母，使其不再是回文串并且使其字典序最小

• 先考虑只有一个字母的情况
  此时拼尽全力改变都还是回文串，所以返回空串 “”

• 然后对于其余回文串

• 首先我们考虑如何破坏回文串
  如果回文串字符是偶数个，那么首位一一呼应，改变任意一个字符都会破坏它
  如果字符是奇数个，那么除了中间的字符，改变其余任意字符同样能破坏它

• 其次由于我们需要其字典序最小，那么毋庸置疑，我们要优先改变靠前的字符，并且将其修改为 ‘a’
  如果考前的字母本就为 ‘a’，那么无论我们怎么修改，都会使字符串变大，所以只
  能去修改其后一位

那么只需要一个循环从头开始枚举字符，如果不是奇数个字符回文串的中间字符且不是 ‘a’，那么我们就可以将其变为 ‘a’，然后退出循环。
如果循环结束都没有找到可以改变的字符，那么说明除了奇数个字符回文串的中间字符外都是 ‘a’，那么便只能修改最后一个字符为 ‘b’，才能是字典序最小

代码如下↓

char* breakPalindrome(char* palindrome) {
    int n=strlen(palindrome);
    if(n==1)
    {
        return "";
    }
    else if(n%2)//个数是奇数个，改变中间字符无用
    {
        int f=1;
        for(int i=0;i<n;i++)
        {
            if(i==n/2)
            {
                continue;
            }
            if(palindrome[i]>'a')
            {
                palindrome[i]='a';
                f=0;
                break;
            }
        }
        if(f)
        {
            palindrome[n-1]='b';
        }
    }
    else
    {
        int f=1;
        for(int i=0;i<n;i++)
        {
            if(palindrome[i]>'a')
            {
                palindrome[i]='a';
                f=0;
                break;
            }
        }
        if(f)
        {
            palindrome[n-1]='b';
        }
    }
    return palindrome;
}