5.最长回文子串(中等)|Java刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

题目描述

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/lo…

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

示例 1：

输入：s = “babad”

输出：”bab”

解释：”aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”

输出：”bb”

示例 3：

输入：s = “a”

输出：”a”

示例 4：

输入：s = “ac”

输出：”a”

提示：

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

题目解析

首先，明确一下回文串就是正着读和反着读都一样的字符串。

比如说字符串 aba 和 abba 都是回文串，因为它们对称，反过来还是和本身一样。反之，字符串 abac 就不是回文串。

动态规划

还是老一套，动态规划三步走

• 分解为子问题 如果字符串s是一个回文串，那么在这个回文串前和后加上同一个字符，那么新的字符串一定也是回文串了，比如"aba"是回文串，前后分别加上"a"，变成"aabaa"也是回文串

• 状态定义 dp[i][j]表示示s[i...j] 是否是回文串

• 状态方程推导 根据第一步就很容易得到状态方程了dp[i][j] = dp[i + 1][j - 1] && s[i]== s[j]

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[chars.length][chars.length];
        int start = 0;
        int end = 0;
        for (int j = 1; j < chars.length; j++) {
            for (int i = 0; i < j; i++) {
                if (chars[i] == chars[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (j - i > end - start) {
                        start = i;
                        end = j;
                    }
                }
            }
        }

        return s.substring(start, end + 1);
    }
}
复制代码

总结

时间复杂度：O(n²)，因为要把dp数组填满，数组的大小是n*n

因为新建了dp数组，这里的空间空间复杂度也是O(n²)，这个方法并不是最优解，但是用来学习动态规划还是挺好的

我觉得动态规划三步走中主要的难点还是分解为子问题，但是只要能把问题分解为子问题，这个问题也就迎刃而解了。很多题目分解子问题不是那么明显，我一般都要去试，在纸上比划比划，找到规律 ，离解决问题也就不远了。