圣狐网-专业源码交易-源码商城-外包接单

热门搜索: 直播    短视频    小程序   

LeetCode上的最长回文子串

分类:圣狐资讯 时间:2023-11-26 23:51 浏览:32
概述
题目描述给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1:输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。示例 2:输入: "cbbd"输出: "bb"分析此题是一道比较经典的字符串题目,可以使用中心扩展算法或者动态规划算法进行求解。中心扩展算法:其中一种常见的
内容

题目描述

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:
输入: "cbbd"
输出: "bb"

分析

此题是一道比较经典的字符串题目,可以使用中心扩展算法或者动态规划算法进行求解。

中心扩展算法:
其中一种常见的解法是基于中心扩展的思想,具体步骤如下:

1.对于字符串s的每个字符,以该字符为中心向左右两侧扩展,找到以该字符为中心的最长回文子串。

2.遍历完所有字符后,比较所有最长回文子串的长度,找到其中长度最长的一个即可。

时间复杂度:O(n^2),空间复杂度:O(1)

动态规划算法:
建立一个 n * n 的矩阵 dp,其中 dp[i][j] 表示 s 中从 i 到 j 这段子串是否为回文串。
若 dp[i][j] 为 true,则说明 s 的子串 s[i:j] 为回文串。
状态转移方程为 dp[i][j] = dp[i+1][j-1] && s[i] == s[j],即 s[i:j] 为回文串,当且仅当 s[i+1:j-1] 为回文串且 s[i] == s[j]。

时间复杂度:O(n^2),空间复杂度:O(n^2)

具体实现细节可以参考下面的代码实现。

中心扩展算法

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String ans = "";
        for (int i = 0; i < n; i++) {
            // 找到以 i 为中心的最长回文子串
            int left = i, right = i;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            if (right - left - 1 > ans.length()) {
                ans = s.substring(left + 1, right);
            }
            // 找到以 i 和 i+1 为中心的最长回文子串
            left = i;
            right = i + 1;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            if (right - left - 1 > ans.length()) {
                ans = s.substring(left + 1, right);
            }
        }
        return ans;
    }
}

动态规划算法

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int l = 0; l nl++) {
            for (int i = 0; i < ni++) {
                int j = i + l;
                if (j >
= n) {
                    break;
                }
                if (l == 0) {
                    dp[i][j] = true;
                } else if (l == 1) {
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    dp[i][j] = (dp[i+1][j-1] && s.charAt(i) == s.charAt(j));
                }
                if (dp[i][j] && l + 1 > ans.length()) {
                    ans = s.substring(i, j+1);
                }
            }
        }
        return ans;
    }
}




评论
联系我们
客服热线: 0371-89908359
客服QQ:
投诉建议:
时间: 9:00-21:00
联系客服
售前咨询 售后咨询 联系客服
0371-89908359
手机版

扫一扫进手机版
返回顶部