97. Interleaving String

https://leetcode.com/problems/interleaving-string/description/

问字符串s3是否由s1和s2插接而成。string match问题用DP。action分别为让s1[i-1]或s2[j-1]和s3[i+j-1] match。dp[i][j]表示s1前i个和s2前j个能否构成s3前i + j个。由于循环最开始的就是对应了i=1和j=1的情况，也就是从s3[1]开始，因此初始化时要分别把i=0和j=0初始化。

/*
 * @lc app=leetcode id=97 lang=cpp
 *
 * [97] Interleaving String
 *
 * https://leetcode.com/problems/interleaving-string/description/
 *
 * algorithms
 * Hard (28.73%)
 * Likes:    905
 * Dislikes: 50
 * Total Accepted:    120.6K
 * Total Submissions: 418.9K
 * Testcase Example:  '"aabcc"\n"dbbca"\n"aadbbcbcac"'
 *
 * Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and
 * s2.
 * 
 * Example 1:
 * 
 * 
 * Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
 * Output: true
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
 * Output: false
 * 
 * 
 */
class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        const int M = s1.size(), N = s2.size();
        if (s3.size() != M + N) return false;
        vector<vector<bool>> dp(M + 1, vector<bool>(N + 1));
        dp[0][0] = true;
        for (int i = 1; i <= M; ++i) {
            if (s1[i - 1] == s3[i - 1] && dp[i - 1][0]) dp[i][0] = true;
            else break;
        }
        for (int j = 1; j <= N; ++j) {
            if (s2[j - 1] == s3[j - 1] && dp[0][j - 1]) dp[0][j] = true;
            else break;
        }
        for (int i = 1; i <= M; ++i)
        {
            for (int j = 1; j <= N; ++j)
            {
                const char c1 = s1[i - 1], c2 = s2[j - 1], c3 = s3[i + j - 1]; 
                if (c1 == c3 && dp[i - 1][j] || c2 == c3 && dp[i][j - 1]) dp[i][j] = true;
            }
        }
        return dp[M][N];
    }
};