【LeetCode】5. 最长回文子串

比眉伴天荒 2022-05-03 00:28 185阅读 0赞

**题目链接**：[https://leetcode-cn.com/problems/longest-palindromic-substring/description/][https_leetcode-cn.com_problems_longest-palindromic-substring_description]

#### 题目描述 ####

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

#### 示例 ####

输入: “babad”  
输出: “bab”  
注意: "aba"也是一个有效答案。

输入: “cbbd”  
输出: “bb”

#### 解决方法 ####

方法1：**暴力法**。选出所有子字符串可能的开始和结束位置，并检验它是不是回文，时间复杂度为O(n^3)。  
方法2：**动态规划**。时间复杂度为O(n^2)  
（1）优化函数：求len(dp\[i\]\[j\])的最大值  
**dp\[i\]\[j\]=true，如果以i开始以j结束的子串是回文子串**  
**dp\[i\]\[j\]=false ，其他情况**  
（2）状态转移方程：**dp\[i\]\[j\]=(dp\[i+1\]\[j−1\] and S\_i==S\_j\})**  
初始化:长度为1和2的回文

class Solution { 
    public:
        string longestPalindrome(string s) { 
            if (s.size()<=1) return s;
            
            bool dp[1001][1001]={ false};
            int maxSublen=1, start=0;
            //初始化dp
            for (int i=0;i<s.size();i++){ 
                dp[i][i]=true;
                if (i<s.size()-1 && s[i]==s[i+1]){ 
                    dp[i][i+1]=true;
                    maxSublen=2;
                    start=i;
                }
            }
            //dp转移
            for (int len=3;len<=s.size();len++){ //len表示子串长度
                for (int i=0;i<=s.size()-len;i++){ 
                    dp[i][i+len-1]=(dp[i+1][i+len-2] && (s[i]==s[i+len-1]));
                    if (dp[i][i+len-1]){ 
                        maxSublen=len;
                        start=i;
                    }
                }
            }
            //得到结果
            return s.substr(start,maxSublen);
        }
    };

[https_leetcode-cn.com_problems_longest-palindromic-substring_description]: https://leetcode-cn.com/problems/longest-palindromic-substring/description/