You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

005.最长回文串-Longest Palindromic Substring

. 1 min read

Longest Palindromic Substring

Analysis: Dynamic Programming

To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes.

Consider the case "ababa". If we already knew that "bab" is a palindrome, it is obvious that "ababa" must be a palindrome since the two left and right end letters are the same.

Define $P(i,j)$ as following:

$$ \begin{equation}
P(i, j)=\left{
\begin{array}{lr}
\text{true,}&\quad\text{if the substring } S_i \dots S_j \text{ is a palindrome} \
\text{false,} &\quad\text{otherwise.}
\end{array}
\right.
\end{equation} $$

Therefore,

$$P(i,j)=(P(i+1,j−1) \land S_i==S_j)$$

The base cases are:

$$P(i, i) = true$$

$$P(i, i+1) = (S_i == S_{i+1})$$

Complexity Analysis

  • Time complexity : $O(n^2)$. This gives us a runtime complexity of $O(n^2)$.
  • Space complexity : $O(n^2)$. It uses $O(n^2)$ space to store the table.

[scode type="yellow"]

  • 这道题中由动态规划的递推公式可知,在矩阵中,当前位置由其右下角的单元及字符串本身决定。
  • 因此在自底向顶的设计中,应该优先填充左下角的部分
    • i--
    • j++
      其中 i 表示横,j 表示纵
      [/scode]

My solution: 38ms

class Solution {
public String longestPalindrome(String s) {
        int len = s.length();
        if (len == 0)   return "";
        char[] str = s.toCharArray();        
        boolean[][] dp = new boolean[len][len];     
        // default: ∀i∀j(dp[i][j] == false)
        int maxLen = 0;
        int maxLeft = 0;
        int maxRight = 0;
        /* base case: */
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
            if (i + 1 < len && str[i+1] == str[i]) {
                dp[i][i+1] = true;
                maxLen = 1;
                maxLeft = i;
                maxRight = i + 1;
            }
        }
        /* using dynamic programming */
        // enumerate right boundry of the substring
        for (int j = 0; j < len; j++) {             
            // enumerate left boundry of the substring
            for (int i = j - 2; i >= 0; i--) {      
                dp[i][j] = str[i] == str[j] && dp[i+1][j-1];
                if(dp[i][j] && j - i + 1 > maxLen){
                    maxLen = j - i + 1;
                    maxLeft = i;
                    maxRight = j;
                }
            }
        }
        return s.substring(maxLeft, maxRight + 1);
    }
}