来源：力扣（LeetCode）
链接：
https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述

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

题目分析

动态规划

用 P(i,j) 表示字符串第 i 到 j 个字母组成的串是否为回文串：

• P(i,j) = true，字符串第 i 到 j 个字母组成的子串是回文
• P(i,j) = false，其他情况

存在动态规划方程： P(i,j) = P(i + 1,j + 1) && s(i) == s(j)

• s(i) == s(j) : s 的第 i 和 j 个字母相同
• 若 i == j ，P(i,j) = true

代码实现

public class LongestPalindrome_5 {

    public static void main(String[] args) {
        LongestPalindrome_5 main = new LongestPalindrome_5();
        String result = main.longestPalindrome("dddddababad");
        System.out.println("result:" + result);
    }


    public String longestPalindrome(String s) {
        int len = s.length();
        if (len == 1) {
            return s;
        }
        int begin = 0;
        int maxLen = 1;

        boolean[][] result = new boolean[len][len];

        char[] charArray = s.toCharArray();
        // 初始化
        for (int i = 0; i < len; i++) {
            result[i][i] = true;
        }

        for (int sbLen = 2; sbLen <= len; sbLen++) {
            for (int i = 0; i < len; i++) {
                int end = i + sbLen - 1;
                // 小心数组越界
                if (end >= len) {
                    break;
                }

                if (charArray[i] == charArray[end]) {
                    // 长度为 2 且字符相同
                    if (sbLen == 2) {
                        result[i][end] = true;
                    } else {
                        result[i][end] = result[i + 1][end - 1];
                    }
                } else {
                    result[i][end] = false;
                }

                // 取最大长度
                if (result[i][end] && maxLen < sbLen) {
                    maxLen = sbLen;
                    begin = i;
                }
            }


        }


        return s.substring(begin, begin + maxLen);
    }

}

运行结果：

复杂度

• 时间复杂度：O(n^2)，其中 n 是字符串长度。
• 空间复杂度：O(n^2)，存储动态规划状态需要的空间。

好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！