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:

$$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.$$

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); } }