Longest Palindromic Substring
Given a string $s$, find the longest palindromic substring in $s$. You may assume that the maximum length of $s$ is $1000$.
Example 1:
Input: "babad"Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
Let $p[i][j]$ be a table that states whether the substring $s_i\ldots s_j$ is a palindrome or not. Note that any substring of $length = 1$ can be considered as a palindrome. The following equation describes the recurrence.
$p[i][j] =
\begin{cases}
true , & \text{if $l = 1$} \\[2ex]
s_i == s_j, & \text{if $l = 2$} \\[2ex]
p[i+1][j-1]\; and \; s_i == s_j, & \text{if $len \gt 2$}
\end{cases}$
Procedure LONGEST-PALINDROME-SUBSTRING takes a String as it’s input. It stores $p[i][j]$ values in a table $p[1 \ldots n][1 \ldots n]$ and it computes the entries in row-major order.
**Input:** $s$ input string
**Output:** the longest palindromic substring in $s$
$LONGEST-PALINDROME-SUBSTRING(s)$
$\phantom{{}++{}}$ $n \gets s.length$
$\phantom{{}++{}}$ let $p[1 \ldots n][1 \ldots n]$ be a new table
$\phantom{{}++{}}$ $start \gets 1$
$\phantom{{}++{}}$ $l \gets 1$
$\phantom{{}++{}}$ `for` $i = 1$ to $n$
$\phantom{{}++{}}$$\phantom{{}++{}}$ $p[i][i] \gets true$
$\phantom{{}++{}}$ `for` $i = 1$ to $n - 1$
$\phantom{{}++{}}$$\phantom{{}++{}}$ $p[i][i + 1] \gets s_i == s_{i + 1}$
$\phantom{{}++{}}$$\phantom{{}++{}}$ `if` $p[i][i + 1]$
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $l \gets 2$
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $start \gets i$
$\phantom{{}++{}}$ `for` $len = 3$ to $n$
$\phantom{{}++{}}$$\phantom{{}++{}}$ for $i = 1$ to $n - len + 1$
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $j \gets i + len - 1$
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $p[i][j] \gets s_i == s_j \; and\; p[i+1][j-1]$
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ `if` $p[i][j]$
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $l \gets len$
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $start \gets i$
$\phantom{{}++{}}$ return $s_{start} \ldots s_{start + l - 1}$
And here’s the code.
Analysis
Time complexity : $Θ(n^2)$Space complexity: $Θ(n^2)$ to store the table.
Comments
Post a Comment