leetcode最長回文サブストリングC++版

タイトルの説明:
文字列sを指定すると、sの中で最も長い回文サブ列が見つかります.sの最大長さは1000と仮定できます.
例1:

  : "babad"
  : "bab"
  : "aba"         。

例2:

  : "cbbd"
  : "bb"

ソリューション:
動的計画法を採用する:回文文字列のサブストリングも回文であり、例えばp[i,j](iからjで終わるサブストリングを表す)は回文文字列であり、p[i+1,j-1]も回文文字列である.これで最長回文子列が一連の列子問題に分解される.最長回文サブストリングは連続することが要求されるため、iはサブストリングの開始座標であり、jはサブストリングの終点座標であり、iおよびjはいずれも0以上文字列長len未満であり、i<=jであり、このようなストリングの長さはj−i+1で表すことができる.私たちは長さ1の子列から順に遍歴し、長さ1の子列は必ず回文であり、その長さは1である.次に、s[i]がs[i+1]に等しい限り、長さが2のサブ列が順次遍歴する.次に、長さが2より大きいサブストリングは、回文サブストリングであるという性質を満たすためには、s[i]がs[j]に等しくなければならず、両端を除いたサブストリングs[i+1...j-1]も必ず回文サブストリングであり、サブ問題から順次増大して解くので、[i...j]の問題を解く場合、それより規模の小さい問題は結果的に直接使用できるようになった.
C++コードは以下の通りです.

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        int maxlen = 0;
        int start;
        bool p[1000][1000] = {false};
        for (int i = 0; i<len;i++){
            p[i][i] = true;
            if (i<len && s[i] == s[i+1]){
                p[i][i+1] = true;
                maxlen = 2;
                start = i;
            }
        }
        for (int l = 3; l<len; l++){
            for (int i = 0; i < len-l; i++){
                int j = l+i-1;
                if (p[i+1][j-1] && s[i] == s[j]){
                    p[i][j] = true;
                    maxlen = l;
                    start = i;
                }
            }
        }
        if (maxlen > 2)
            return s.substr(start,maxlen);
        return NULL ;  
 }
};