原文链接: https://leetcode-cn.com/problems/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.

Example 3:

Input: palindrome = "aa"
Output: "ab"

Example 4:

Input: palindrome = "aba"
Output: "abb"

 

Constraints:

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

中文题目

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

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

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

 

示例 1：

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

示例 2：

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

示例 3：

输入：palindrome = "aa"
输出："ab"

示例 4：

输入：palindrome = "aba"
输出："abb"

 

提示：

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

通过代码

高赞题解

思路

首先如果字符串长度为奇数，则字符串中间的那个字符无论怎么改，字符串都是回文串。
如：aba，b字符无论怎么改，字符串都还是回文串。

回文串前半段和后半段是相互对应的，因此只要遍历一半就好了。

首先遍历前半段，遇到不为a的字符就直接将其替换成a，然后直接return结果。
如果前半段都是a，则说明后半段也都是a，说明字符串要么类似aabaa，要么类似aaaaaa。
直接将最后1个字符改成b就好了。

代码

[-java代码]
class Solution {
    public String breakPalindrome(String palindrome) {
        int len = palindrome.length(), half = (len - 2) >> 1;
        if (len < 2) return "";
        char[] ch_arr = palindrome.toCharArray();
        for (int i = 0; i <= half; ++i)
            if (ch_arr[i] > 'a') {
                ch_arr[i] = 'a';
                return String.valueOf(ch_arr);
            }
        ch_arr[len - 1] = 'b';
        return String.valueOf(ch_arr);
    }
}

[-c++代码]
class Solution {
public:
    string breakPalindrome(string palindrome) {
        size_t len = palindrome.size(), half = (len - 2) >> 1;
        if(len < 2) return "";
        for (size_t i = 0; i <= half; ++i)
            if (palindrome[i] > 'a') {
                palindrome[i] = 'a';
                return palindrome;
            }
        palindrome[len - 1] = 'b';
        return palindrome;
    }
};

[-python3代码]
class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        str_len = len(palindrome)
        if str_len < 2:
            return ""
        for idx in range(str_len >> 1):
            if palindrome[idx] > 'a':
                return palindrome[:idx] + 'a' + palindrome[idx+1:]
        return palindrome[:str_len-1] + 'b'
        # str_len = len(palindrome)
        # char_list = list(palindrome)
        # for idx in range(str_len >> 1):
        #     if char_list[idx] > 'a':
        #         char_list[idx] = 'a'
        #         return ''.join(char_list)
        # char_list[str_len - 1] = 'b'
        # return ''.join(char_list)

统计信息

通过次数	提交次数	AC比率
6180	13280	46.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言