LeetCode 题解-5. Longest Palindromic Substring

对Leetcode 5. Longest Palindromic Substring 题目的求解。

Problem Description#

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1#

1
Input: "babad"
2
Output: "bab"
3
Note: "aba" is also a valid answer.

Example 2#

1
Input: "cbbd"
2
Output: "bb"s

Analysis#

这道题的题意为从字符串的子串中找出最长的回文串．而回文可以递归定义，所以我们可以靠动态规划来解决这个问题．复杂度为O(n^2).

Solution 1: dp#

1
class Solution {
2
    public static String longestPalindrome(String s) {
3
        int l = s.length();
4
        if (l == 0) return s;
5
        int max = 0;
6
        int max_i = 0;
7
        int max_j = 0;
8
        int dp[][] = new int [l][l];
9
        for (int i = 0; i < l; ++i){
10
            dp[i][i] = 1;
11
        }
12
        for (int i = 1; i <= l - 1; ++i){
13
            for (int j = 0; j < l - i; ++j){
14
                if (s.charAt(j) == s.charAt(j+i)){
15
                    if (i == 1) dp[j][j+i] = 1;
16
                    else dp[j][j+i] = dp[j+1][j+i-1];
17
                }
18
                if (dp[j][j+i] == 1){
19
                    if (i + 1 > max){
20
                        max = i + 1;
21
                        max_i = j;
22
                        max_j = j+i;
23
                    }
24
                }
25
            }
26
        }
27
        return s.substring(max_i, max_j+1);
28
    }
29
}

Solution 2: dfs solution with stack#

还有一种思路就是先选定回文的中心，在进行扩展，遍历所有可能的中心得到最长的结果．

1
public static String longestPalindrome(String s) {
2
    //each palindrome is centered
3
    if (s.length() == 0) return s;
4
    int l = 0;
5
    int r = 0;
6
    int max_l = 0; int max_r = 0; int max_ = 0;
7
    for (int i = 0; i < s.length() - 1; ++i){
8
        //extend(i, i, )
9
        l = i;r = i;
10
        while ( l >= 0 && r <= s.length() - 1 && s.charAt(l) == s.charAt(r)) {
11
            l --; r ++;
12
        }
13
        if (max_ < r - l - 1){
14
            max_ = r - l - 1;
15
            max_l = l+1; max_r = r-1;
16
        }
17
        //extent(i,i+1)
18
        l = i;r = i+1;
19
        while ( l >= 0 && r <= s.length() - 1 && s.charAt(l) == s.charAt(r)) {
20
            l --; r ++;
21
        }
22
        if (max_ < r - l - 1){
23
            max_ = r - l - 1;
24
            max_l = l+1; max_r = r-1;
25
        }
26
    }
27
    return s.substring(max_l, max_r+1);
28
}