LeetCode 5. Longest Palindromic Substring(C++ダイナミックプランニング)

5.Longest Palindromic Substringは、指定された文字列sを意味し、文字列sの最長の回文サブ列を見つけて出力する.回文とは、文字列が左から右へ読み返すのと右から左へ読むのと同じです.注意問題説明最長文字数1000とする
Example 1: Input: “babad” Output: “bab” Note: “aba” is also a valid answer.
Example 2: Input: “cbbd” Output: “bb”
構想1:(brute force暴力解O(n^3)はタイムアウトする)文字列sに対して,そのすべてのサブストリングを取り,取り出したそのサブストリングがエコーストリングであるか否かを判断し,最長のエコーストリング出力を見つければよい.
サブストリングを取る具体的な方法は、サブストリングの先頭サブストリングiと、終了サブストリングjとを設定し、全てのサブストリングを二重ループして取り出すサブストリングがエコーストリングであるか否かを判断することである(サブストリングO(n^2)).
回文列を判断するには、文字列sを逆順にして、逆順後の文字列と元の文字列が等しいか否かを判断し、等しいことを回文列(ここで逆順時間複雑度はO(n))とし、サブ列を取るたびに回文列であるか否かを判断する必要があるため、総時間複雑度はO(n^3)となる.
C++コード

//brute force
class Solution {
public:
    string longestPalindrome(string s) {
        if(s=="")
            return "";
        int max = 0;
        string result;
        for(int i = 0; imax){
                    result = substr;
                    max = substr.length();
                }
            }
        }
        return result;
    }
    
    bool isPalindromic(string substring){//the time complexity of this function is O(n^3)
        string copy = substring;
        reverse(copy.begin(), copy.end());
        return copy == substring;
    }
    
};

ヒントを見て、この問題はダイナミックな計画を使うことができると言ったが、まだ手がかりがなく、プッシュ式が見つからない.構想2:ダイナミックプランニング(O(n^2))は、s.length()x s.length()の2次元配列dpを設定し、配列dp[i][j]=1は文字列sのサブ列si...sj(サブ列siからsj)はエコー列、dp[i][j]=0はこのサブ列が非エコー列であることを示す.
ダイナミックプランニングの境界条件は、dp[i][i]=1(長さ1のサブストリングは必ず回文ストリング)dp[i][i+1]=(s[i]=s[i+1])(長さ2のサブストリングの2文字が等しい場合は回文サブストリング)である.
状態遷移方程式:dp[i][j]=(dp[i+1][j-1]&&s[i]==s[j])であり、1つのサブストリング自体が回文ストリングである場合、そのサブストリングの左右に同じ任意の文字を付けるか回文ストリングを加えるか
以上のことから,この問題は,すべての長さが1のサブストリングが回文ストリングであるか否かを判断してから,すべての長さが2のサブストリングが回文ストリングであるか否かを判断し,次いで長さが3,4,...のサブストリングが回文ストリングであるか否かを順次判断するサブストリングの長さであることが分かる.これにより、配列dpの繰返しは、主対角線(左上から右下の線)で順次上方に繰返しられることが分かる.
複雑度解析時間複雑度O(n^2):取サブ列は依然としてO(n 2)であり、エコー列がO(1)であるか否かを判断するので、総時間複雑度はO(n 2)空間複雑度O(n^2):状態配列dpを維持し、サイズはs.length x s.length()
この問題の使用動態計画はいつもとは違って、一般的な問題型は私は一般的に再帰から動規に変換し、再帰時の過剰な繰り返し計算を減らして効率を高めるが、この問題はサブ列が回文列であるかどうかを判断するために動規を使って判断する.実際に回文列に多くの繰り返し計算があると判断するからだ.小さなサブストリングの判断は、後続のより大きなサブストリングの判断に役立つ(既存のサブストリングの両側に文字を増やしてO(1)を判断することを考慮する)ため、ゲージを用いることで時間的複雑さを低減することができる.ゲージを使わないと、文字列をバカに繰り返すたびに返信列かどうかを判断し、sが長すぎるとタイムアウトしやすい.
C++コード

class Solution {
public:
    string longestPalindrome(string s) {
        if(s=="")
            return "";
        vector > dp(s.size(), vector(s.size(), 0));
        int start = 0, end = 0, max = 0;
        //initialize the basic case
        for(int i = 0;imax){
                        start = i;
                        end = j;
                        max = j-i;
                    }
                }
            }
        }
        return s.substr(start, end+1-start);
    }
};