solution.md

# 交错字符串

<p>给定三个字符串 <code>s1</code>、<code>s2</code>、<code>s3</code>，请你帮忙验证 <code>s3</code> 是否是由 <code>s1</code> 和 <code>s2</code><em> </em><strong>交错 </strong>组成的。</p><p>两个字符串 <code>s</code> 和 <code>t</code> <strong>交错</strong> 的定义与过程如下，其中每个字符串都会被分割成若干 <strong>非空</strong> 子字符串：</p><ul>	<li><code>s = s<sub>1</sub> + s<sub>2</sub> + ... + s<sub>n</sub></code></li>	<li><code>t = t<sub>1</sub> + t<sub>2</sub> + ... + t<sub>m</sub></code></li>	<li><code>|n - m| <= 1</code></li>	<li><strong>交错</strong> 是 <code>s<sub>1</sub> + t<sub>1</sub> + s<sub>2</sub> + t<sub>2</sub> + s<sub>3</sub> + t<sub>3</sub> + ...</code> 或者 <code>t<sub>1</sub> + s<sub>1</sub> + t<sub>2</sub> + s<sub>2</sub> + t<sub>3</sub> + s<sub>3</sub> + ...</code></li></ul><p><strong>提示：</strong><code>a + b</code> 意味着字符串 <code>a</code> 和 <code>b</code> 连接。</p><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0097.Interleaving%20String/images/interleave.jpg" style="width: 561px; height: 203px;" /><pre><strong>输入：</strong>s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"<strong><br />输出：</strong>true</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"<strong><br />输出：</strong>false</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>s1 = "", s2 = "", s3 = ""<strong><br />输出：</strong>true</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>0 <= s1.length, s2.length <= 100</code></li>	<li><code>0 <= s3.length <= 200</code></li>	<li><code>s1</code>、<code>s2</code>、和 <code>s3</code> 都由小写英文字母组成</li></ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    bool res;
    string s1 = "aabcc";
    string s2 = "dbbca";
    string s3 = "aadbbcbcac";
    res = sol.isInterleave(s1, s2, s3);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();

        if (len1 + len2 != len3)
            return false;

        bool f[len1 + 1][len2 + 1];
        f[0][0] = true;
        for (int i = 0; i < len1 + 1; i++)
        {
            for (int j = 0; j < len2 + 1; j++)
            {

                if (j > 0)
                {
                    f[i][j] = f[i][j - 1] && s3[i + j - 1];
                }
                if (i > 0)
                {
                    f[i][j] = f[i][j] || (f[i - 1][j] && s3[i + j - 1]);
                }
            }
        }
        return f[len1][len2];
    }
};
```
## 选项


### A

```cpp
class Solution
{
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[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++)
            {
                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 dp[m][n];
    }
};
```

### B

```cpp
class Solution
{
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();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= m; ++i)
            dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
        for (int i = 1; i <= n; ++i)
            dp[0][i] = dp[0][i - 1] && (s2[i - 1] == s3[i - 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 + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
            }
        return dp[m][n];
    }
};
```

### C

```cpp
class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        int s1_len = s1.size();
        int s2_len = s2.size();
        int s3_len = s3.size();
        if (s1_len + s2_len != s3_len)
            return false;
        if (s1_len == 0 || s2_len == 0)
            return s1 + s2 == s3;
        vector<vector<bool>> dp(s1_len + 1, vector<bool>(s2_len + 1));
        dp[0][0] = true;
        for (int i = 0; i <= s1_len; i++)
        {
            for (int j = 0; j <= s2_len; j++)
            {
                if (dp[i][j])
                {
                    if (i < s1_len && s1[i] == s3[i + j])
                        dp[i + 1][j] = true;
                    if (j < s2_len && s2[j] == s3[i + j])
                        dp[i][j + 1] = true;
                }
            }
        }
        return dp[s1_len][s2_len];
    }
};
```