97. 交错字符串

原题链接：97. 交错字符串

solution:

动态规划

① 状态表示:dp[i][j]表示字符串s1[0 ~ i - 1] 和 s2[0 ~ j - 1]能否构成字符串s3[i - 1 + j]
② 属性:可以构成true，不能构成false
③ 转移方程: 

dp[i][j] = (dp[i - 1][j] & (s1[i - 1] == s3[i - 1 + j])) || (dp[i][j - 1] & (s2[j - 1] == s3[i - 1 + j]));

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(),n = s2.size(),k = s3.size();
        if(m + n != k) return false;    
        vector> dp(m + 1 ,vector (n + 1, false));
        //dp[i][j] 表示s1[0 ~ i - 1] 和 s2[0 ~ j - 1] 能否构成s3[i + j - 1];
        dp[0][0] = true;

        //初始化
        for(int i = 1;i <= m;i++) { //i在字符串s1和s3中对应下标为i - 1
            dp[i][0] = dp[i - 1][0] & (s1[i - 1] == s3[i - 1]);
        }

        for(int j = 1;j <= n;j++) {
            dp[0][j] = dp[0][j - 1] & (s2[j - 1] == s3[j - 1]);
        }

        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
               dp[i][j] = (dp[i - 1][j] & (s1[i - 1] == s3[i - 1 + j])) || (dp[i][j - 1] & (s2[j - 1] == s3[i - 1 + j]));
            }
        }

        return dp[m][n];
    }
};