Ad-Hoc问题：在字符串中删改字符

摘要:

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，今天我们来看一个在字符串中删改字符使得某个指标最大的问题，在一个数字中删改数位使得某个指标最大也是类似的问题。

这类问题往往是经过分析后，得出使得指标最大的操作数位的规则，特定问题需要特定分析，没有固定套路，这是 Ad-Hoc 问题的特点。

有一个点值得提一下，有时容易错误地将这类问题理解为贪心问题。贪心算法是解决涉及到多阶段决策的优化问题的。如果问题具有最优子结构，也就是整体问题的最优解包含了子问题的最优解，同时还具有贪心选择性质，也就是每一阶段都做出当前状态下的最优选择会导致整体问题也得到最优解，那么就可以每一阶段直接选择局部最优解即可，这个过程就是贪心算法。

而这种在字符串中删改字符的问题，不涉及多阶段决策这一特点，因此谈不上贪心算法。

题目

• 1328. 破坏回文串

给你一个由小写英文字母组成的回文字符串 palindrome ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小 ，且 不是 回文串。

请你返回结果字符串。如果无法做到，则返回一个 空串 。

如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，”abcc” 字典序比 “abcd” 小，因为不同的第一个位置是在第四个字符，显然 ‘c’ 比 ‘d’ 小。

提示：

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

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

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

题解

算法: 分析问题

在 s 中更改一个字符，要使得字典序最小，自然的想法就是更改的字符尽量将其改为 ‘a’，因为 a 是字母表中的最小字符。

另一方面我们还希望将一个字符改为 ‘a’ 的这个字符的位置尽可能靠左，因为字典序是按照从左到右的顺序对比各个位的，综上就有了大致的算法框架：

从左到右枚举各个字符，将遇到的第一个非 ‘a’ 的字符改为 ‘a’ 即可。

由于输入 s 是回文串，且改字符后所得的字符串不能是回文串，因此只需要枚举 0 ~ n/2-1 这些字符即可，比如当 n=8 或 n=9，枚举的就是 0,1,2,3 这些字符。

一个特殊情况是整个串的字符全是 ‘a’，这样就将最右边的字符改为 ‘b’ 即可。

还有一个情况是如果字符串只有一个字符，则无论怎么改，所得结果都是回文，这样就返回 -1。

代码 (C++)

class Solution {
public:
    string breakPalindrome(string palindrome) {
        int n = palindrome.size();
        if(n == 1)
            return "";
        for(int i = 0; i < n / 2; ++i)
        {
            if(palindrome[i] != 'a')
            {
                palindrome[i] = 'a';
                break;
            }
            if(i == n / 2 - 1)
            {
                palindrome[n - 1] = 'b';
                break;
            }
        }
        return palindrome;
    }
};

代码 (Python)

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        n = len(palindrome)
        if n == 1:
            return ""
        s = list(palindrome)
        for i in range(n // 2):
            if s[i] != 'a':
                s[i] = 'a'
                break
            if i == n // 2 - 1:
                s[n - 1] = 'b'
                break
        return "".join(s)

---