iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 11
0
自我挑戰組

有志者,事竟成。系列 第 11

Day11 LeetCode #5 Longest Palindromic Substring

題目描述

給定一個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^


上一篇
Day10 第三十四題LeetCode #4 Median of Two Sorted Arrays
下一篇
Day12 LeetCode #6 ZigZag Conversion
系列文
有志者,事竟成。19

尚未有邦友留言

立即登入留言