LeetCode 97. 交错字符串（DP）

示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

class Solution {	//C++
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.size()+s2.size() != s3.size())
        	return false;
        int m = s1.size(), n = s2.size(), i, j, k;
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        // dp[i][j] 表示 s1取了i个，s2取了 j 个，可以匹配s3前面的
        dp[0][0] = 1;
        for(i = 0; i < m; i++) 
        	if(s1[i] == s3[i])
        		dp[i+1][0] = 1;
            else
                break;
        for(i = 0; i < n; i++)
        	if(s2[i] == s3[i])
        		dp[0][i+1] = 1;
            else
                break;

        for(i = 1; i <= m; ++i)
        	for(j = 1; j <= n; j++)
        	{	//要求 i，j 状态，该状态下s3是第i+j个字符
        		k = i+j;
        		if(s1[i-1] == s3[k-1])//s1的第i个字符匹配
        			dp[i][j] |= dp[i-1][j];
    			if(s2[j-1] == s3[k-1])//s2的第j个字符匹配
    				dp[i][j] |= dp[i][j-1];
        	}
    	return dp[m][n];
    }
};

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m+n != len(s3):
            return False;
        dp = [[0]*(n+1) for _ in range(m+1)]
        dp[0][0] = 1
        for i in range(m):
            if s1[i] == s3[i]:
                dp[i+1][0] = 1
            else:
                break
        for i in range(n):
            if s2[i] == s3[i]:
                dp[0][i+1] = 1
            else:
                break
        for i in range(1,m+1):
            for j in range(1,n+1):
                k = i+j
                if s1[i-1] == s3[k-1]:
                    dp[i][j] |= dp[i-1][j]
                if s2[j-1] == s3[k-1]:
                    dp[i][j] |= dp[i][j-1]
        return True if dp[m][n] else False