How to Break a Palindrome String by Replacing a Character?

  • 时间：2020-09-11 08:23:45
  • 分类：网络文摘
  • 阅读：174 次

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn’t a palindrome. After doing so, return the final string. If there is no way to do so, return the empty string.

Example 1:
Input: palindrome = “abccba”
Output: “aaccba”

Example 2:
Input: palindrome = “a”
Output: “”

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

Hints:
How to detect if there is impossible to perform the replacement? Only when the length = 1.
Change the first non ‘a’ character to ‘a’.
What if the string has only ‘a’?
Change the last character to ‘b’.

Algorithms to Break the Palindrome String

If the string is a one-character Palindrome, then it isn’t possible to do so since every one-character string is a Palindrome. Then, we can scan the first half of the Palindrome to see if it is all ‘a’. If it is, then we change the last character to ‘b’. Otherwise, we change the first non ‘a’ character to ‘a’. This will make a non Palindrome with the smallest lexicographically order.

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    string breakPalindrome(string palindrome) {
        if (palindrome.size() == 1) {
            return "";
        }
        for (int i = 0; i < palindrome.size() / 2; ++ i) {
            if (palindrome[i] != 'a') {
                return palindrome.substr(0, i) + 'a' + 
                    palindrome.substr(i + 1);
                // or the following should work as well
                // palindrome[i] = 'a';
                // return palindrome;
            }
        }
        return palindrome.substr(0, palindrome.size() - 1) + 'b';
        // or the following should work
        // palindrome[palindrome.size() - 1] = 'b';
        // return palindrome;
    }
};
class Solution {
public:
    string breakPalindrome(string palindrome) {
        if (palindrome.size() == 1) {
            return "";
        }
        for (int i = 0; i < palindrome.size() / 2; ++ i) {
            if (palindrome[i] != 'a') {
                return palindrome.substr(0, i) + 'a' + 
                    palindrome.substr(i + 1);
                // or the following should work as well
                // palindrome[i] = 'a';
                // return palindrome;
            }
        }
        return palindrome.substr(0, palindrome.size() - 1) + 'b';
        // or the following should work
        // palindrome[palindrome.size() - 1] = 'b';
        // return palindrome;
    }
};

Java:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public String breakPalindrome(String palindrome) {
        if (palindrome.length() == 1) return "";
        for (int i = 0; i < palindrome.length() / 2; ++ i) {
            if (palindrome.charAt(i) != 'a') {
                return palindrome.substring(0, i) + 'a' +
                    palindrome.substring(i + 1);
            }
        }
        return palindrome.substring(0, palindrome.length() - 1) + 'b';
    }
}
class Solution {
    public String breakPalindrome(String palindrome) {
        if (palindrome.length() == 1) return "";
        for (int i = 0; i < palindrome.length() / 2; ++ i) {
            if (palindrome.charAt(i) != 'a') {
                return palindrome.substring(0, i) + 'a' +
                    palindrome.substring(i + 1);
            }
        }
        return palindrome.substring(0, palindrome.length() - 1) + 'b';
    }
}

Python (s[:-1] to trim the last character):

1
2
3
4
5
6
7
8

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        if len(palindrome) == 1:
            return ""
        for i in range(len(palindrome) // 2):
            if palindrome[i] != 'a':
                return palindrome[:i] + 'a' + palindrome[i + 1:]
        return palindrome[:-1] + 'b';
class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        if len(palindrome) == 1:
            return ""
        for i in range(len(palindrome) // 2):
            if palindrome[i] != 'a':
                return palindrome[:i] + 'a' + palindrome[i + 1:]
        return palindrome[:-1] + 'b';

Javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * @param {string} palindrome
 * @return {string}
 */
var breakPalindrome = function(palindrome) {
    if (palindrome.length === 1) {
        return "";
    }
    for (let i = 0; i < Math.floor(palindrome.length / 2); ++ i) {
        if (palindrome[i] != 'a') {
            return palindrome.substr(0, i) + 'a' + 
                palindrome.substr(i + 1);
        }
    }
    return palindrome.substr(0, palindrome.length - 1) + 'b';
};
/**
 * @param {string} palindrome
 * @return {string}
 */
var breakPalindrome = function(palindrome) {
    if (palindrome.length === 1) {
        return "";
    }
    for (let i = 0; i < Math.floor(palindrome.length / 2); ++ i) {
        if (palindrome[i] != 'a') {
            return palindrome.substr(0, i) + 'a' + 
                palindrome.substr(i + 1);
        }
    }
    return palindrome.substr(0, palindrome.length - 1) + 'b';
};

All implementations run O(N) in the worst case. O(1) constant is required.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
号称“零脂肪”的乳品同样会引发肥胖　 宣称“高钙”的食品补钙效果未必好　 广告中的“高膳食纤维”食品并不健康　 宣传的“零热量”饮品真的很不靠谱　 宣称健康的“全谷物”饮品营养仅一般　 国家食品药品监督管理总局正式挂牌　 办公室白领防电脑辐射食品大盘点　 春分节气饮食养生不同体质的食疗　 问题奶粉不断涌现，奶粉监管怎么了？　 保健食品营销骗局令人深恶痛绝　
评论列表
添加评论