[C++] LeetCode 97. インタリーブ文字列

タイトル
3つの文字列s 1,s 2,s 3が与えられ、s 3がs 1とs 2のインタリーブから構成されているかどうかを検証する.例えば、所与:s1="aabcc"、s2="dbbca"、s3="aadbbcbcac"、戻るtrue.当s3="aadbbbaccc",返false.
問題解
この問題は動的計画で解くことが考えられる.dp(i,j)表示s1の前i文字列とs2の前j文字列が構成できるかs3の前i+j文字列.1、もしs1[i]==s3[i+j-1]、ならdp(i,j)=dp(i-1,j)2、もしs2[j]==s3[i+j-1]、ならdp(i,j)=dp(i,j-1)注意点:上記の2つのケースが同時に発生する可能性があるため、つまりs1[i]==s3[i+j-1]とs2[j]==s3[i+j-1]が同時に満足しているので、そのうちの1つが成立すればdp[i][j]=1となるので、いずれも満足している場合は考慮しなければならない.
コード#コード#

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1=s1.size(),len2=s2.size(),len3=s3.size();
        if(len1+len2!=len3)return false;
        if(len3==0)return true;
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        for(int i=1;i<=len1&&s1[i-1]==s3[i-1];i++){
            dp[i][0]=1;
        }
        for(int i=1;i<=len2&&s2[i-1]==s3[i-1];i++){
            dp[0][i]=1;
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                int k=i+j-1;
                if(s1[i-1]==s3[k]&&dp[i-1][j]==1){
                    dp[i][j]=1;
                }
                if(s2[j-1]==s3[k]&&dp[i][j-1]==1){
                    dp[i][j]=1;
                }
            }
        }
        return dp[len1][len2];
    }
};