[LeetCode] 1328. Break a Palindrome 破壞回文串

Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

Example 2:

Input: palindrome = "a"
Output: ""
Explanation: There is no way to replace a single character to make "a" not a palindrome, so return an empty string.

Constraints:

1 <= palindrome.length <= 1000
palindrome consists of only lowercase English letters.

這道題給了一個只有小寫字母的回文串，現在讓我們改動一個字母，使其變為非回文串，且字母順序最小。對于回文串，想必大家都不陌生，就是從首尾兩端往中間看，對應兩端的字母都依次相等，除了奇數個字母中的最中間第一個例外，比如 aabaa 中間的b。題目中還說了，若無法使其變為非回文串，則返回空串。那么就來想一下，什么情況下無法變為非回文串，其實就是當只有一個字母時，根據回文串的定義，單個字母也算回文串，所以無論將該字母換成任何其他字母時，其仍然是回文串。這里可以在開頭判斷一下，若給定的回文串長度為1，則直接返回空串。

若長度超過1的話，就要考慮一下具體的置換策略了，根據例子1的字符串 "abccba" 來分析，第一個字母是a，不可能再變的更小，而第二個字母是b，可以通過變成a，來變為非回文串，且字母順序最小，于是策略就是從前往后遍歷，遇到第一個非a的字母，改變為a就行了，由于回文串的對稱性，只需要遍歷前半個字符串就行了。但其實題目中漏掉了一種情況，比如 "aabaa" 或者 "aaaa"，這兩個字符串的前半部分都是a，而將前半段中的任何的a變為b，雖然變為了非回文串，但卻不是字母順序最小了，正確的方法應該是將整個回文串的最后一個a變為b，這樣才能得到字母順序最小的非回文串，參見代碼如下：

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

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1328

參考資料：

https://leetcode.com/problems/break-a-palindrome/

https://leetcode.com/problems/break-a-palindrome/solutions/489774/java-c-python-easy-and-concise/

LeetCode All in One 題目講解匯總(持續更新中...)