最长回文子串

发表于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode每日一题，5. Longest Palindromic Substring

先看题目描述

大意就是给定一个字符串，返回其中的最长回文子串

算法和思路

这题一开始只想到了暴力解法，觉得这个方法肯定不好。后面就去看题解，发现可以用动态规划优化

动态规划

  • dp[i][j] 表示字符串的子串 s[i, j](左闭右闭) 是否是回文子串，若为 true，则是回文子串; 否则不是
  • 状态转移方程:
    • 若 i - j <= 2，dp[i][j] = s[i] == s[j]
    • 否则，dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]

初始化时，单个字符一定是回文串，因此将 dp[i][i] 置为 true

一旦 dp[i][j] = true，则计算其长度，若长度大于当前维护的最大长度，则更新最大长度，并记录其起始位置，最后根据记录的最大长度和起始位置返回子串即可

注意：由于需要先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，所以填表顺序很重要

算法源码

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