Leetcode # 5. Longest Palindromic Substring (Manacher’s Algorithm)

https://leetcode.com/problems/longest-palindromic-substring/

Solution

Dynamic Programming

\begin{align*}
& \text{定義 } P(i, j) \text{ 為：} \\
& P(i, j)=
\begin{cases}
True & \text{, if the substring } S_i…S_j \text{ is a palindrome } \\
False & \text{, otherwise }
\end{cases} \\\\
& 即 \\
& P(i, j)=(P(i+1, j-1) \land S_i==S_j) \\\\
& 並且 \\
& P(i, i)=True \\
& P(i, i + 1)=( S_i == S_{i+1} )
\end{align*}

※ Key Point：
將dp[0]和dp[1]獨立出來用一維for迴圈初始化，否則會Time Limit Exceeded

Time Complexity: O(n ^ 2)
Space Complexity: O(n ^ 2)

class Solution:
  def longestPalindrome(self, s: str) -> str:
    dp = [set() for i in range(len(s))]

    for i in range(len(s)):
      dp[0].add((i, i))
      if i < len(s) - 1 and s[i] == s [i + 1]: 
        dp[1].add((i, i + 1)) 
    
    for l in range(2, len(s)): 
      for i in range(len(s)): 
        j = i + l 
        if j >= len(s):
          break
        if (i + 1, j - 1) in dp[j - i - 2] and s[i] == s [j]:
          dp[j - i].add((i, j))

    lps_i = max([i for i in range(len(s)) if dp[i]])
    start, end = list(dp[lps_i])[0]
    return s[start:end + 1]

Manacher’s Algorithm

\begin{align}
& P_x = palindrome_x := L_x + C_x + R_x in S, \\
& C_x \text{ is } S[x], \\
& \overline{str} := reversed(str) \\
& L_x = \overline{R_x} = reversed(R_x) \\
& radius_x = r_x := len(L_x) \\
& I_S(n) := \text{the index of } n \text{ in } S \\
\\
& \exists P_x, P_y; len(P_y) < len(P_x) \land  y < x \\
& \text{let } y’ := x + (x – y) \text{ namely } \left| x – y \right| = \left| x – y’ \right| \\
& \text{Case 1: } I_S(L_x[0]) < I_S(L_y[0])\\
& \quad \text{let } L_x = a + P_y + b, \\
& \quad \text{then } P_x = L_x + C_x + R_x = (a + P_y + b) + C_x + (\overline{b} + P_y + \overline{a}) \\
& \quad len(P_{y’}) \geq len(P_x) \text{ only if } a = \overline{b} \quad \Rightarrow \Leftarrow \\
& \quad \text{∴ } len(P_{y’}) < len(P_x) \\
& \text{Case 2: } I_S(L_y[0]) < I_S(L_x[0])\\
& \text{Case 3: } I_S(L_y[0]) == I_S(L_x[0])\\
\end{align}

Ref: Wikipedia

Last Updated on 2023/08/16 by A1go