Re: [閒聊] 每日LeetCode

[z2147483648 (溢傷了喇)]

: 5. Longest Palindromic Substring
: 給一個字串s，回傳最長的子字串，其順序跟倒序長一樣。
: Input: s = "babad"
: Output: "bab" 或 "aba"

想法：

感覺可以用DP寫，但我DP不好@@

改用回文特性中心擴散法

從中間檢查兩邊index+i, index-i是否相等，來判斷是否是回文

如果是回文的話順便算一下是否是目前最大

然後迭代每個index找出最大值

奇數很好懂 就是index-i, index+i

偶數推了一下 每次檢查index-i, index+i-1

如果不是就break(利用odd_continue/even_continue兩個Flag控制)


Python死腦筋的用了while if 寫來寫去，不小心遇到邊界陷阱

C++改用function包起來簡單美觀多了



========== Python


class Solution:
    def longestPalindrome(self, s: str) -> str:
        maxLen = 0
        maxret = ""

        for i in range(len(s)):
            j = 0
            odd_continue = True
            even_continue = True
            while(i - j >= 0 and i + j - 1 < len(s)):
                if (odd_continue and i+j < len(s) and s[i-j] == s[i+j]):
                    if maxLen < 2*j + 1:
                        maxret = s[i-j: i+j+1]
                        maxLen = 2*j + 1
                else:
                    odd_continue = False

                if (j > 0):
                    if (even_continue and s[i-j] == s[i+j-1]):
                        if maxLen < 2*j:
                            maxret = s[i-j: i+j]
                            maxLen = 2*j
                    else:
                        even_continue = False
                if (not odd_continue and not even_continue):
                    break
                j += 1

        return maxret


=========== C++

class Solution {
public:
    string longestPalindrome(string s) {
        int maxLen = 0;
        string maxString = "";
        for (int i = 0; i < s.size(); ++i)
        {
            vector<int> res = findMaxPalindrome(s, i, i);
            int st = res[0];
            int end = res[1];
            if (end - st + 1 > maxLen)
            {
                maxLen = end - st + 1;
                maxString = s.substr(st, end-st+1);
            }
            res = findMaxPalindrome(s, i, i+1);
            st = res[0];
            end = res[1];
            if (end - st + 1 > maxLen)
            {
                maxLen = end - st + 1;
                maxString = s.substr(st, end-st+1);
            }
        }
        return maxString;

    }
    vector<int> findMaxPalindrome(string s, int center, int center2)
    {
        int count = 0;
        while(center >= 0 && center2 < s.size())
        {
            if (s[center] == s[center2])
            {
                count++;
                center--;
                center2++;
            }
            else
            {
                break;
            }
        }
        center++;
        center2--;
        return {center, center2};
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.12.199 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698427714.A.427.html
推 wwndbk: 大師
→ z2147483648: 樓上才是大師