最长回文子串（手撕lc)

谁借莪１个温暖的怀抱￠ 2022-08-29 12:57 97阅读 0赞

## 题目描述 ##

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

## 示例 ##

输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。

输入：s = "cbbd"
    输出："bb"

输入：s = "a"
    输出："a"

## 代码展示以及思路分析 ##

### 经历的第一个错误代码 ###

#include<algorithm>
    #include<cstdio>
    #include<cmath>
    #include<iostream>
    
    
    class Solution {
        
    public:
        bool Judge(string s)
        {
        
            string tmp=s;
            reverse(s.begin(),s.end());
            if(tmp==s)
            {
        
                return true;
            }
            else{
        
                return false;
            }
        }//判断是否为回文
        string longestPalindrome(string s) {
        
                  string ans="";
                  int n=s.size();
                  int max=0;
                  for(int i=0;i<n;i++)
                  {
        
                      for(int j=i+1;j<=n;j++)
                      {
        
                           string result=s.substr(i,j);//返回i到j的子串，然后进行判断是否为回文
                           if(Judge(result)&&result.length()>max)
                           {
        
                               ans=s.substr(i,j);
                               max=max>result.length()?Max:result.length();
                           }
                      }
                  }  
                  return ans;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70 1]

可是，按照其中一个题解想出的暴力解法并不完美，说明这暴力解决法没有理解好或者说仍有缺陷。

### DP（动态规划） ###

看了题解，发现暴力法只能解决部分测试，很多情况下会因为超时而跑不出正确的结果。因此自己尝试去理解题解所说的DP办法。[具体解释可以点击这里][Link 1].

因为对于一个子串而言，如果本身是回文子串，去掉头尾的元素仍是回文子串。例如对于字符串“ababa"，去掉了首尾的a仍然是回文。也就是说，只有 s\[i+1:j−1\] 是回文串，并且 s 的第 i和 j 个字母相同时，s\[i:j\] 才会是回文串。（这些讨论的长度是字符串大于2的情况下）  
对于长度为1的字符串肯定是回文，对于长度为2的字符串仅当两个字母相同时才为回文串

#include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    class Solution {
        
    public:
        string longestPalindrome(string s) {
        
            int n = s.size();
            if (n < 2) {
        
                return s;
            }
    
            int maxLen = 1;
            int begin = 0;
            // dp[i][j] 表示 s[i..j] 是否是回文串
            vector<vector<int>> dp(n, vector<int>(n));
            // 初始化：所有长度为 1 的子串都是回文串
            for (int i = 0; i < n; i++) {
        
                dp[i][i] = true;
            }
            // 递推开始
            // 先枚举子串长度
            for (int L = 2; L <= n; L++) {
        
                // 枚举左边界，左边界的上限设置可以宽松一些
                for (int i = 0; i < n; i++) {
        
                    // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                    int j = L + i - 1;
                    // 如果右边界越界，就可以退出当前循环
                    if (j >= n) {
        
                        break;
                    }
    
                    if (s[i] != s[j]) {
        
                        dp[i][j] = false;
                    } else {
        
                        if (j - i < 3) {
        
                            dp[i][j] = true;
                        } else {
        
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    }
    
                    // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                    if (dp[i][j] && j - i + 1 > maxLen) {
        
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
            return s.substr(begin, maxLen);
        }
    };

![在这里插入图片描述][7f1c63ec96d740928163c51db54dae98.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70]: /images/20220829/da65d35571714440b99e4f4e5222651a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/94af627c63874b88bdc0aaf6011f490e.png
[Link 1]: https://www.zhihu.com/question/23995189
[7f1c63ec96d740928163c51db54dae98.png]: /images/20220829/84a352aa62194dc596aa1af6663ac779.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/01b66d8806a541f68b360bedf97da352.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220829/39e2889ad1f44805a1db62d4b890d467.png