Two C++ O(N^2) methods


  • 0
    C
    class Solution {
    public:
    /**method 1 中心扩展法**//*
        int cen1,cen2,len,r;
        void check(int pos,const string &s){
            int i=1;
            while(pos-i>=0 && pos+i<s.size() && s[pos-i]==s[pos+i]){
                i++;
            }
            if(2*(i-1)+1>len){
                len = 2*(i-1)+1;
                r = i-1;
                cen1 = pos;
                cen2 = -1;
            }
            
        }
        void check(int pos1,int pos2,const string &s){
            int i = 1;
            while(pos1-i>=0 && pos2+i<s.size() && s[pos1-i]==s[pos2+i]){
                i++;
            }
            if(2*i>len){
                len = 2*i;
                r = i-1;
                cen1 = pos1;
                cen2 = pos2;
            }
        }
        string longestPalindrome(string s) {
            if(s.empty()) return s;
            cen1 = 0;cen2 = -1;
            len = 1; r = 0;
            for(int i=0;i<s.size()-1;++i){
                check(i,s);
                if(s[i]==s[i+1])
                    check(i,i+1,s);
            }
            if(cen2==-1){
                return s.substr(cen1-r,len);
            }else{
                return s.substr(cen1-r,len);
            }
        }
    */
    /**method 2 dp**/
         string longestPalindrome(string s) {
            vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
            int pos = 0,len = 1;
            for(int i=0;i<s.size();++i) {
                dp[i][i] = true;
                if(i+1<s.size() && s[i]==s[i+1]) {
                    dp[i][i+1] = true;
                    pos = i;
                    len = 2;
                }
            }
            for(int l = 3;l<=s.size();++l){
                for(int i=0;i<s.size()-l+1;++i){
                    int j = i+l-1;
                    if(s[i]==s[j] && dp[i+1][j-1]){
                        dp[i][j] = true;
                        pos = i;
                        len = l;
                    }
                }
            }
            return s.substr(pos,len);
         }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.