[LeetCode][C++][005]Longest Palindromic Substring(最長回文サブストリング)

//
//  LeetCode_5_LongestPalindrome.cpp
//  arithmetic
//
//  Created by li on 2018/5/15.
//  Copyright © 2018  li. All rights reserved.
//  
//
//　　Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000,and there exists one unique longest palindromic substring.
//    
//
//　　       S，           ，              1000，             

//    
//       :          ，               
//    :         ，    ，  abcba abba。
//  s[i,j]（   i   j     ）      ，  s[i+1,j-1]       ，                    
//       O（N^2）,     O(N^2)
//

#include "LeetCode_5_LongestPalindrome.hpp"
string LeetCode_5_LongestPalindrome::longestPalindrome(string s){
    int dp[s.size()][s.size()],left = 0,right = 0,len = 0;
    for(int i=0;isize();i++){
        for(int j=0;jsize();j++){
            dp[i][j] = 0;
        }
    }
    for(int i = 0; i < s.size(); ++i){
        for (int j = 0; j < i; ++j) {
            dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));//              （   1）       ，           1
            if(dp[j][i] && len < i-j+1){//         ，           ，           left      right    
                len = i-j +1;//index + 1    
                left = j;
                right = i;
            }
        }
        dp[i][i] = 1;

//        for(int k=0;k
//            for(int n=0;n
//            cout<
//            }
//            cout<
//        }
//
//        cout<
    }
    return s.substr(left,right-left + 1);

}

int LeetCode_5_LongestPalindrome::main(int argc, const char * argv[]){

    string s = "wetyuytsdfgfds";
    LeetCode_5_LongestPalindrome longestPalindrome;
    string subs = longestPalindrome.longestPalindrome(s);
    std::cout<<"LongestPalindrome:"<< subs <<:endl class="hljs-keyword">return 0;
}