005.最长回文串-Longest Palindromic Substring

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

 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
26
27
28
29
30
31
32
33
34
35
36
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);
    }
}