[Day 18] Leetcode 1328. Break a Palindrome (C++)

前言

今天来做九月每日挑战的今天这题1328. Break a Palindrome。这题不是考验程序能力，而是逻辑问题XD 归纳完规则的瞬间即可解题~

想法

我是先依照我的想法解题，後来官方解其实有更好的解法，如果不想绕远路可以直接拉到下面优化解~

初始解法

所谓Palindrome在leetcode真的超级常出现，中文是"回文"，就是对称的string，正着跟倒着会一样，例如abcba或 ~~元智幼稚园~~ (一时只能想到这个举例QQ 无恶意)

顺到一提，leetcode基础题检查是否为palindrome的作弊python3解法就是if(s==s[::-1])秒解XD

总之这题就是有一个原为回文的string，要在只改一个字的情况下且是字母顺最小的情况下破坏这个回文，如果怎麽改都不行就回传空字串。那我们就可以开始整理规则了：

什麽情况下会怎麽改都不行?
A: 只有在字串只有1个字的时候会怎麽改都不行
可以改的情况下要怎麽让字母顺序最小?
A: 第一个字改成'a'
什麽情况下第一个字改成'a'不成立? 要怎麽改?
A: 第一个字本来就是'a'的时候第一个字改成'a'没用；就往後去改第一个不是'a'的字母，但若字串是单数的话正中间的改了也没用。
如果都不能改成'a'的情况下要怎麽改?
A: 把最後一个字改成'b'就一定可以。
接下来就是把以上的规则直接翻译成程序就好了：

class Solution {
public:
    string breakPalindrome(string palindrome) {
        // check if impossible
        int l=palindrome.length();
        if(l==1){
            return "";
        }
        // turn the first one to 'a' if the first is not 'a'
        if(palindrome[0]!='a'){
            return "a"+palindrome.substr(1,l-1);
        }
        // the first one is a, check if there are no a characters
        for(int i=1;i<l;++i){
            // not a and not the middle one in odd string
            if(palindrome[i]!='a' && (l%2==0 || i!=l/2)){
                return palindrome.substr(0,i)+"a"+palindrome.substr(i+1,l-1-i);
            }
        }
            
        // otherwise, change the last one to b
        return palindrome.substr(0,l-1)+"b";
    }
};

感觉比起其他题目轻松简单许多，题目下面有个留言蛮好笑的:

从这个问题领悟到的人生哲学: 破坏比修理一个东西简单很多?

优化解

按照我的逻辑写完之後，看到官方其实也有提供solution，才发现有可以优化之处：

检查是不是能改成'a'只需要检查前半段就好，连判断是不是中间点也不用了。因为原本是回文，所以如果前半都是a，後半也肯定都是a，结案。
不需要用substr，直接用palindrome[i]去修改那个位置就好了。会没用这样改纯粹是写python写习惯了XD python的string不能这样改。

依据以上两点改完之後程序就变得简洁许多了：

class Solution {
public:
    string breakPalindrome(string palindrome) {
        // check if impossible
        int l=palindrome.length();
        if(l==1){
            return "";
        }
        // check if there are no a characters
        for(int i=0;i<l/2;++i){
            if(palindrome[i]!='a'){
                palindrome[i]='a';
                return palindrome;
            }
        }
        // otherwise, change the last one to b
        palindrome[l-1]='b';
        return palindrome;
    }
};

时间复杂度是O(n)，因为只需要遍历前半段1/2*n就好了。