Loading...
墨滴

公众号:offer多多

2021/08/06  阅读:34  主题:橙心

数据结构与算:最长子串

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

解题思路

代码

class Solution {
public:
    string longestPalindrome(string s) {
       
       int indexBegin =0;
       int indeEnd =0;
       int  n = s.size();

       //Palindrome

       //01 
      vector<vector<bool>> dp(n,vector<bool>(n,false))//dp[start][end]  N>end >=start 


      //02 [aaa] 
      //[aaa] 
      //[aa]
      //[a]
      //if: s[start ] =s[end]  && 
      // /dp[start][end] = dp[start+1][end-1](一定存在) , end -1 >=start +1  

      //03 
       for(int end =0; end <n;end++)
       {
           forint start =0; start <= end; start++)
           {
                 if (s[start] ==s[end])
                 {   //case1 
                     if(end -start >=2)
                     {
                          dp[start][end] = dp[start+1][end-1];
                     }else
                     {
                         //case2  i[0 -]
                         dp[start][end]  = true;
                     }
                 }
                  //回文子串 --最长的
                 if( dp[start][end]  == true && end-start > indeEnd- indexBegin )
                 {
                     indexBegin = start;
                     indeEnd = end;
                 }
           }
       }

       return s.substr(indexBegin,indeEnd-indexBegin+1);
    }
};

公众号:offer多多

2021/08/06  阅读:34  主题:橙心

作者介绍

公众号:offer多多