leetcode 5 Longest Palindromic Substring
z
 2017-12-13 10:36:00  

5. 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
2
3
4
5
6
Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

1
2
3
Input: "cbbd"

Output: "bb"

这道题在卜老师的算法课上做过。

用动态规划的思想，开辟一个n*n的二维数组dp

当dp[i][j]是回文且s[i-1]==s[j+1]时，新的子字符串也是回文

注意临界点的处理，上述条件只适用于j-i > 2的情况

当j-i <= 2 时，相当于 (i) () (j) 和 (i) (j) 这两种情况，只需要判断s[i] 是否等于s[j] 即可。

临界条件同样也可以改为

1
if((i-j >=2 && s.charAt(j)==s.charAt(i) && dp[j+1][i-1])|| (i-j<=1 && s.charAt(j)==s.charAt(i)))

因为当j-i == 2时，dp[i+1][j-1] 表示的是长度为1的字符串，已经在之前判断过，可以放在第一个判断里面。

注意：问清楚，当字符串为：abcdefg这种形式时，返回什么。

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
class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 0){
            return "";
        }
        if (s.length() == 1){
            return s;
        }
        int n = s.length();
        int max = 0;
        String result = s.substring(0,1);
        
        boolean dp[][] = new boolean[n][n];
        
        for(int i=0; i<n; i++){
            for (int j=0; j<=i; j++){
                if((i-j >2 && s.charAt(j)==s.charAt(i) && dp[j+1][i-1])|| (i-j<=2 && s.charAt(j)==s.charAt(i))) {
                    dp[j][i] = true;
                    if(max < i-j){
                        max = i-j;
                        result = s.substring(j,i+1);
                    }
                }
            }
        }
        return result;
    }
}