5. 最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

输入输出

1
2
3
4
5
6
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

输入：s = "cbbd"
输出："bb"

基本思路

  1. 暴力破解 时复$O(n^3)$ 无法通过测试

  2. 中心扩散法 算法分析：

    1. 从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。
    2. s.charAt(i) == s.charAt(left) 首先往左寻找与当期位置相同的字符，直到遇到不相等为止。
    3. s.charAt(i) == s.charAt(right) 然后往右寻找与当期位置相同的字符，直到遇到不相等为止。
    4. s.charAt(left) == s.charAt(right) 最后左右双向扩散，直到左和右不相等。
    5. 时复$O(n^2)$ n是字符串长度长度为1和2的回文中心有n和n-1个，每个回文中心最多向外扩展$O(n^2)$次 空复$O(1)$

  3. 动态规划法 算法分析：

    1. 设置一个boolean dp[l][j]
    2. 如果dp[l][r] = true 就需要判断dp[l-1][r+1]是否回文 只需判断字符在这两个位置是否相同
    3. 进入正题，动态规划关键是找到初始状态和状态转移方程：
      1. 初始状态，l=r 时，此时 dp[l][r]=true
      2. 状态转移方程，dp[l][r]=true 并且(l-1)和（r+1)两个位置为相同的字符，此时 dp[l-1][r+1]=true
    4. 时复$O(n^2)$ n是字符串长度 空复$O(n^2)$ 存储动态规划状态需要的二维数组空间

java实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// 中心扩散法
class Solution {
    public String longestPalindrome(String s) {
        int strlen = s.length();
        if(s == null || strlen == 0) return "";
        int left = 0, right = 0;
        int len = 1, maxStart = 0, maxLen = 0;
        for(int i = 0; i < strlen; i++){
            left = i - 1;
            right = i + 1;
            while(left >= 0 && s.charAt(i) == s.charAt(left)){
                left--;
                len++;
            }
            while(right < strlen && s.charAt(i) == s.charAt(right)){
                right++;
                len++;
            }
            while(left >= 0 && right < strlen && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
                len += 2;
            }
            if(len > maxLen){
                maxLen = len;
                maxStart = left;
            }
            len = 1;// 考虑也有'a'这样的字符串也算
        }
        return s.substring(maxStart + 1, maxStart + maxLen + 1);
    }
}

// 动态规划
class Solution {
    public String longestPalindrome(String s) {
        int strlen = s.length();
        if(s == null || strlen < 2){
            return s;
        }

        int maxStart = 0, maxEnd = 0, maxLen = 1;
        boolean[][] dp = new boolean[strlen][strlen];

        for(int r = 1; r < strlen; r++){
            for(int l = 0; l < r; l++){
                if(s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l+1][r-1])){
                    //此处为了兼容 aa（r-l=1）和aba（r-l=2）这两种回文串
                    //'a'这种单独字符串38行已经判断了
                    dp[l][r] = true;
                    if(r - l + 1 > maxLen){
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd+1);
    }
}

// 暴力破解
class Solution {
    public String longestPalindrome(String s) {
        String ans = "";
        int max = 0;
        int len = s.length();
        for(int i = 0; i < len; i++){
            for(int j = i + 1; j <= len; j++){
                String test = s.substring(i, j);
                if(isPalindrome(test) && test.length() > max){
                    ans = s.substring(i, j);
                    max = Math.max(max, ans.length());
                }
            }
        }
        return ans;
    }
    
    public boolean isPalindrome(String s){
        int len = s.length();
        for(int i = 0; i < len/2; i++){
            if(s.charAt(i) != s.charAt(len - 1 - i)){
                return false;
            }
        }
        return true;
    }
}