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

关注

发布于: 刚刚

题目描述

给你一个字符串 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

原文链接:【http://xie.infoq.cn/article/f00625094404b71ecf4abf84d】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

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

题目描述

思路分析

通过代码

总结

HQ数字卡

评论