最长回文字符串

我会带着你远行 2022-09-09 13:48 136阅读 0赞

# 最长回文字符串 #

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

示例 1：

输入：s = “babad”  
输出：“bab”  
解释：“aba” 同样是符合题意的答案。  
示例 2：

输入：s = “cbbd”  
输出：“bb”  
示例 3：

输入：s = “a”  
输出：“a”  
示例 4：

输入：s = “ac”  
输出：“a”

#include<iostream>
    #include<vector>
    #include<string>
    class Solution { 
    public:
        string longestPalindrome(string s) { 
            int n=s.size();
            int length=1;
            int a=0;
            vector<vector<int>> dp(n,vector<int>(n));
            //初始化dp
            for(int i=0;i<n;i++)
            { 
                dp[i][i]=true;
            }
            //设置步长
            for(int d=2;d<=n;d++)
            { 
                //从左侧开始的位置
                for(int i=0;i<n;i++)
                { 
                    int j=d+i-1;
                    if(j>=n)
                    break;
                    else{ 
                        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];
                            }
                        }
                    }
                if(dp[i][j]&&j-i+1>length)
                { 
                    length=j-i+1;
                    a=i;
                }
                }
                
            }
            return s.substr(a,length);
        }
    };

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-palindromic-substring  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。