【LeetCode】Interleaving String

DP。二维数组isIntr[i][j]表示s3前i+j个字符是否是s1前i个字符与s2前j个字符的interleaving。那么有如下关系式
isIntr[i][j]=((isIntr[i-1][j]&&s1[i-1]==s3[i+j-1])||(isIntr[i][j-1]&&s2[j-1]==s3[i+j-1]));
最后isIntr[s1.length()][s2.length()]即为结果。

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