LeetCode5-最长回文子串

发表于 | 分类于 | | 阅读量
字数统计: 757 字 | 阅读时长 ≈ 3 分钟

题目

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

** 案例1:**

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

** 案例2:**

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

** 案例3:**

1
2
输入：s = "a"
输出："a"

** 案例4:**

1
2
输入：s = "ac"
输出："a"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母（大写和/或小写）组成

解法1

首先我们要理解什么是回文子串，即左右对称的为回文子串。我们在寻找子串的时候只能通过两个循环去寻找子串，于是我们可以先确定右边界，依次右移来获取子串。

回文子串

我们通过边界右移寻找子串比较他们的子串是否相同，如果不同则存到dp[][]的二维数组里面，可以下次使用，这是动态规划的思想，空间置换时间。具体解法代码如下：

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
class Solution {
    public String longestPalindrome(String s) {
        // 如果字符串大小小于1直接返回空串即可
        if(s.length() < 1) {
            return "";
        }
        int length = s.length();

        // 前面校验过空串，这边直接取第一个字符作为初始化字符即可
        String maxStr = s.substring(0,1);
        boolean[][] dp = new boolean[length][length];

        // 对dp数组进行初始化
        for(int i = 0; i < length; i++) {
            dp[i][i] = true;
        }

        for(int right = 1; right < length; right++) {
            for(int left = 0; left < right; left++) {
                // 两端不相等的情况
                if(s.charAt(right) != s.charAt(left)) {
                    dp[right][left] = false;
                    continue;
                } else {
                    // 两端相等的情况
                    if(left + 1 >= right -1) {
                        dp[right][left] = true;
                    } else {
                        dp[right][left] = dp[right - 1][left + 1];
                    }
                    if(dp[right][left] && right - left + 1 > maxStr.length()) {
                        maxStr = s.substring(left, right + 1);
                    }
                }
            }
        }
        return maxStr;
    }
}

解法2

Manacher算法

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
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        String str = addBoundaries(s, '#');
        int sLen = 2 * len + 1;
        int maxLen = 1;

        int start = 0;
        for (int i = 0; i < sLen; i++) {
            int curLen = centerSpread(str, i);
            if (curLen > maxLen) {
                maxLen = curLen;
                start = (i - maxLen) / 2;
            }
        }
        return s.substring(start, start + maxLen);
    }

    private int centerSpread(String s, int center) {
        // left = right 的时候，此时回文中心是一个空隙，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是任意一个字符，回文串的长度是偶数
        int len = s.length();
        int i = center - 1;
        int j = center + 1;
        int step = 0;
        while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
            step++;
        }
        return step;
    }


    /**
     * 创建预处理字符串
     *
     * @param s      原始字符串
     * @param divide 分隔字符
     * @return 使用分隔字符处理以后得到的字符串
     */
    private String addBoundaries(String s, char divide) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        if (s.indexOf(divide) != -1) {
            throw new IllegalArgumentException("参数错误，您传递的分割字符，在输入字符串中存在！");
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            stringBuilder.append(divide);
            stringBuilder.append(s.charAt(i));
        }
        stringBuilder.append(divide);
        return stringBuilder.toString();
    }
}