Interleaving String

97. 交错字符串

分析

初始化：
- 先计算 s1 和 s2 的长度 n 和 m，并检查 s3 的长度是否为 n + m。如果不是，直接返回 false
- 为了方便处理边界情况，我们给 s1、s2 和 s3 的开头加上一个空格 ' '，这样可以简化状态转移的边界处理
状态表示 f：
- f[i][j] 表示由 s1 的前 i 个字符和 s2 的前 j 个字符是否能交错组成 s3 的前 i + j 个字符。
- 初始化 f[0][0] = true，表示空的 s1 和空的 s2 能交错组成空的 s3
动态规划转移：
- 对于每一个 i 和 j，检查当前字符是否匹配：
- 如果 s1[i] 和 s3[i + j] 相等，则可以从 f[i-1][j] 更新到 f[i][j]
- 如果 s2[j] 和 s3[i + j] 相等，则可以从 f[i][j-1] 更新到 f[i][j]
结果返回：
- 最终返回 f[n][m]，即判断 s1 和 s2 是否能够交错组成 s3

时间复杂度

时间复杂度 O(n * m)，其中 n 是 s1 的长度，m 是 s2 的长度

空间复杂度

空间复杂度为 O(n * m)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        int n = s1.size(), m = s2.size();

        // 如果 s3 的长度不等于 s1 和 s2 的长度之和，直接返回 false
        if (s3.size() != n + m)
            return false;

        // 加上空字符方便处理边界情况
        s1 = ' ' + s1;
        s2 = ' ' + s2;
        s3 = ' ' + s3;

        // 初始化状态表示f
        std::vector<std::vector<bool>> f(n + 1, std::vector<bool>(m + 1));

        // 状态转移
        for (int i = 0; i <= n; ++i)
        {
            for (int j = 0; j <= m; ++j)
            {
                if (i == 0 && j == 0)
                    // 起始点，空的 s1 和 s2 可以交错组成空的 s3
                    f[i][j] = true;
                else
                {
                    // 如果 s1[i] == s3[i + j]，则可以从 f[i-1][j] 更新到 f[i][j]
                    if (i && s1[i] == s3[i + j])
                        f[i][j] = f[i - 1][j];
                    // 如果 s2[j] == s3[i + j]，则可以从 f[i][j-1] 更新到 f[i][j]
                    if (j && s2[j] == s3[i + j])
                        f[i][j] = f[i][j] || f[i][j - 1];
                }
            }
        }

        // 返回结果
        return f[n][m];
    }
};