写点什么

【LeetCode】最长回文子串 Java 题解

用户头像
HQ数字卡
关注
发布于: 刚刚

题目描述

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


示例 1:
输入:s = "babad"输出:"bab"解释:"aba" 同样是符合题意的答案。
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/longest-palindromic-substring著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的每日一题是求最长回文子串题目。“回文串”是一个正读和反读都一样的字符串。一个字符也是回文串。

  • 求最长回文子串,我们采用动态规划的方法求解。对于一个子串,如果它是回文串,并且长度大于 2,那么将它首尾的两个字母去除之后,它仍然是个回文串。

  • 我们定义 dp 二维数组表示当前是否是回文串。字符相等的时候为 true。我们枚举子串的长度,从 2 开始,然后枚举首尾字符做判断是否回文,枚举过程中,不断更新最大的长度,代码如下:

通过代码

class Solution {    public String longestPalindrome(String s) {        int n = s.length();        if (n < 2) {            return s;        }
int maxLen = 1; int begin = 0;
boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = true; }
char[] charArray = s.toCharArray(); for (int subStrlength = 2; subStrlength <= n; subStrlength++) { for (int i = 0; i < n; i++) { int j = i + subStrlength - 1; if (j >= n) { break; } if (charArray[i] != charArray[j]) { dp[i][j] = false; } else { if (j - i < 3) { dp[i][j] = true; } else { dp[i][j] = dp[i + 1][j - 1]; } }
if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1; begin = i; }
} }
return s.substring(begin, begin + maxLen); }}
复制代码

总结

  • 上述算法的时间复杂度是 O(n * n), 空间复杂度是 O(n * n)

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 2
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】最长回文子串Java题解