題目描述

給定一個string，請輸出最長的回文子字串。
舉例
s="abbac"
ans="abba"

思路

回文分奇偶兩種判斷法(因程式內容設計，偶數必須在前方)
發現回文，兩邊拓展查看是否為回文。查詢時不會短於目前最長回文的長度。
奇：b(O)→aba(O)→cabad(X)
偶：bb(O)→wbbw(O)→pwbbwk(X)

程式碼

class Solution {
public:
    bool is_Palindromic(string str){
        for (int i=0; i<(str.length()/2); i++)
        {
            if(str[i] != str[str.length()-i-1])
                return false;
        }
        return true;
    }
    string longestPalindrome(string s) {
        string ans,sub;
        int longest=0;
        for(int i=longest;i<s.length();i++)
        {
            for(int j=longest;i-j>=0&&i+j<=s.length();j++)//even palindromic
            {
                sub.assign(s,i-j,2*j);
                if(is_Palindromic(sub))
                    longest=j,ans=sub;
                else
                    break;
            }
        }
        for(int i=longest;i<s.length();i++)
        {
            for(int j=longest;i-j>=0&&i+j<s.length();j++)//odd palindromic
            {
                sub.assign(s,i-j,2*j+1);
                if(is_Palindromic(sub))
                    longest=j,ans=sub;
                else
                    break;
            }
        }
        return ans;
    }
};

心路歷程

我這次玩string的substr發現了一件事 ── assign()的速度比substr()還要快。
另外，一開始其實我的方法並不好，本身就是一個極差的寫法，所以造成了8次TLE→我美麗的過題紀錄就這樣被我華麗的刷掉了。(當時並不覺得自己方法不好，只是不停地把多餘的、不需要重複計算的部分砍掉，所以有了8次)
原先作法
慢慢增大字串，判斷是否為回文。且如果已經有長度n的回文，之後尋找時字串長度要比n+1更大。
舉例 abaab 我會跑
a(O) ab aba(O) abaa abaab baab(O)
所以答案是baab。
雖然答案是正確的，但倘若是在極長的字串中搜尋極短的回文，那效率.....
比如 abcdefghijklmnopqrstuvwxyzy 我要到最後才會知道yzy是回文
靈光一閃
刷題我最討厭的不是碰到WA而是TLE，因為這意味著你其實想法並沒錯，但偏偏作法不好，必須全部重新打過。
然後我說過最近在照顧家裡老人家呢，所以我就先去顧老人家了，顧著的時候就開始在腦袋裡想新演算法。
走走晃晃是有助於思考的，只坐在電腦前面是會變傻瓜的
我就想到了，aba是回文，如果往兩邊發展是cabac也是回文，但如果是cabad的話就不是回文了，這樣就不用再繼續擴展下去。以這樣的思考來看要跑的程式會大幅減少，畢竟要成為回文的機率是很低的。
而這必須要處理的是aba和abba他們偶數奇數i和j的位置不同，拿一張紙寫寫畫畫就可以懂了喔^w^