[动态规划] 5. 最长回文子串

我会带着你远行 2021-11-27 03:50 280阅读 0赞

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

思路：用动态规划的方法，参考题解

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhdGZhdG1vbW8_size_16_color_FFFFFF_t_70][]

class Solution \{  
public:  
    string longestPalindrome(string s) \{  
        int len=s.size();  
        if(len==0||len==1)  
            return s;  
        int start=0;//回文串起始位置  
        int max=1;//回文串最大长度  
        vector<vector<int>>  dp(len,vector<int>(len));//定义二维动态数组  
        for(int i=0;i<len;i++)//初始化状态  
        \{  
            dp\[i\]\[i\]=1;  
            if(i<len-1&&s\[i\]==s\[i+1\])  
            \{  
                dp\[i\]\[i+1\]=1;  
                max=2;  
                start=i;  
            \}  
        \}  
        for(int l=3;l<=len;l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串  
        \{  
            for(int i=0;i+l-1<len;i++)  
            \{  
                int j=l+i-1;//终止字符位置  
                if(s\[i\]==s\[j\]&&dp\[i+1\]\[j-1\]==1)//状态转移  
                \{  
                    dp\[i\]\[j\]=1;  
                    start=i;  
                    max=l;  
                \}  
            \}  
        \}  
        return s.substr(start,max);//获取最长回文子串  
    \}  
\};

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhdGZhdG1vbW8_size_16_color_FFFFFF_t_70]: /images/20211126/9f5acdf2872641bcb32f0c8d2b0210be.png

发表评论取消回复

表情：

评论列表（有 0 条评论，280人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划No30】leetcode5. 最长回文子串

【算法|动态规划No30】leetcode5. 最长回文子串

傷城~/ 2024年04月27日 06:48/ 0 赞/ 16 阅读

相关动态规划之最长回文子串

思路：这类问题通过穷举的办法，判断是否是回文子串并再筛选出最长的，效率很差。使用动态规划的策略来求解，首先从子问题入手，并将子问题的解保存起来，然后在求解后面的问题

傷城~/ 2023年08月17日 17:32/ 0 赞/ 61 阅读

相关 5. 最长回文子串

[5. 最长回文子串][5.] 1、参考资料 [LeetCode 官方题解][LeetCode] 2、题目要求 > 题目描述给定一个字符串 `s`，找到

傷城~/ 2022年12月29日 09:39/ 0 赞/ 149 阅读

相关 5. 最长回文子串

1、题目描述给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1： > 输入: “babad” > 输出: “b

╰半夏微凉°/ 2022年12月21日 09:27/ 0 赞/ 156 阅读

相关 5. 最长回文子串

> 给你一个字符串 s，找到 s 中最长的回文子串。 > > > > 示例 1： > > 输入：s = "babad" > 输出："bab" > 解释："ab

小鱼儿/ 2022年10月16日 10:00/ 0 赞/ 142 阅读

相关 5. 最长回文子串

[https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/][https_leet

川长思鸟来/ 2022年09月08日 03:58/ 0 赞/ 142 阅读

相关 5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2

Bertha 。/ 2022年08月31日 00:48/ 0 赞/ 162 阅读

相关【动态规划】求最长公共子串，最长回文子串

题目 : 给定两个字符串，求出它们之间连续的最长的相同子字符串的长度。 eg : fbaabe，ebaabf，连续最长子串长度为4。注意：求最长回文子串也可以用求最长公

朴灿烈づ我的快乐病毒、/ 2022年08月09日 00:59/ 0 赞/ 201 阅读

相关 5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。示例 1：输入: "babad" 输出: "bab" 注意

红太狼/ 2022年05月20日 04:10/ 0 赞/ 173 阅读

相关 [动态规划] 5. 最长回文子串

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。思路：用动态规划的方法，参考题解 ![watermark_typ

我会带着你远行/ 2021年11月27日 03:50/ 0 赞/ 281 阅读