This page looks best with JavaScript enabled

Leetcode 5 Longest Palindromic Substring

題目大意

給定一字串,回傳最長&最先出現的回文子字串

Problem

Medium
Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 1:

Input: s = "cbbd"
Output: "bb"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

My Solution

基本作法

因為回文的中間必定是回文, 所以判斷方式由中心向兩側延伸, 中心點 ms 的開頭開始選取

以下作法第二層 loop 分為奇偶兩種長度的 substring 判斷

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def longestPalindrome(self, s: str) -> str:
        res, maxl = s[0], 1

        lng = len(s)
        # m := mid index
        # i := index offset
        for m in range(lng):
            for i in range(1+min(m, lng-1-m)):
                l, r = m-i, m+i
                # 0<=l, r<=lng-1 -> 0<=m-i, m+i<=lng-1 -> i<=m, i<=lng-1-m
                if s[l] != s[r]:
                    break
                new_l = 1+2*i  # r-l+1
                if new_l > maxl:
                    res, maxl = s[l:r+1], new_l
            for i in range(1+min(m, lng-2-m)):
                l, r = m-i, m+1+i
                # 0<=m-i, m+1+i<=lng-1 -> i<=m, i<=lng-2-m
                if s[l] != s[r]:
                    break
                new_l = 2+2*i
                if new_l > maxl:
                    res, maxl = s[l:r+1], new_l
        return res

第二層 loop 合併處理

無論一字串長度之奇偶為何, 在其每一個間隔插入一字後長度必為奇數 n + (n+1) = 2n+1

透過此方式轉換, 第二層迴圈只需比對奇數長度之 substring

同時程式看起來較簡潔, 但複雜度不變, 優化成效要看 input data

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def longestPalindrome(self, s: str) -> str:
        sep = '_'
        s = sep + sep.join(s) + sep

        res, maxl = s[:3], 3

        lng = len(s)
        for m in range(lng):
            for i in range(1+min(m, lng-1-m)):
                l, r = m-i, m+i
                if s[l] != s[r]:
                    break
                new_l = 1+2*i
                if new_l > maxl:
                    res, maxl = s[l:r+1], new_l
        return res.replace(sep, '')

某演算法

wip