【面试经典150 | 动态规划】交错字符串_算法

文章目录

写在前面
tag
题目来源
解题思路
- 方法一：动态规划
写在最后

写在前面

tag

【动态规划】【字符串】

题目来源

97. 交错字符串

解题思路

方法一：动态规划

首先进行特判，记字符串 s1 的长度、字符串 s2 的长度、字符串 s3 的长度分别为 m、n 和 t。如果 m + n != t，那么 s3 一定无法由 s1 和 s2 交错组成。

定义状态

在 m + n = t 时，定义 f[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 字符是否能交错组成 s3 的前 i+j 个字符。

转移关系

如果 s1 的第 i 个字符和 s3 的第 i+j 个字符相同，那么 s1 的前 i 个字符和 s2 的前 j 字符是否能交错组成 s3 的前 i+j 个字符 取决于 s1 的前 i-1 个字符和 s2 的前 j 字符是否能交错组成 s3 的前 i+j-1 个字符，即有：

$katex parse error: expected 'eof', got '&' at position 22: \dotsj] = f[i-1][j] &̲ (s_1[i-1] == s\dots$

同理，如果 s2 的第 j 个字符和 s3 的第 i+j 个字符相同，那么 s1 的前 i 个字符和 s2 的前 j 字符是否能交错组成 s3 的前 i+j 个字符 取决于 s1 的前 i 个字符和 s2 的前 j-1 字符是否能交错组成 s3 的前 i+j-1 个字符，即有：

$katex parse error: expected 'eof', got '&' at position 22: \dotsj] = f[i][j-1] &̲ (s_2[j-1] == s\dots$

base case

边界条件为 f[0][0] = true。

最后返回

最终返回 f[m][n]，表示字符串 s3 是否可以右字符串 s1 和 s2 交错形成。

朴素实现代码

class solution {
public:
    bool isinterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size(), t = s3.size();
        if (m + n != t) return false;

        vector<vector<int>> f(m+1, vector<int>(n+1, false));

        f[0][0] = true; // base case 空字符串可以交错形成空字符串
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[i][j] |= f[i-1][j] && (s1[i-1] == s3[p]);
                }
                if (j > 0) {
                    f[i][j] |= f[i][j-1] && (s2[j-1] == s3[p]);
                }
            }
        }
        return f[m][n];
    }
};

使用滚动数组优化空间复杂度。因为这里数组 f 的第 i 行只和第 i−1 行相关，所以我们可以用滚动数组优化这个动态规划，这样空间复杂度可以变成 $o (m)$ 。

空间优化代码

class solution {
public:
    bool isinterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size(), t = s3.size();
        if (m + n != t) return false;

        vector<int> f(n+1, false);

        f[0] = true; // base case 空字符串可以交错形成空字符串
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[j] &= (s1[i-1] == s3[p]);
                }
                if (j > 0) {
                    f[j] |= f[j-1] && (s2[j-1] == s3[p]);
                }
            }
        }
        return f[n];
    }
};

复杂度分析

时间复杂度： $o (mn)$ ， $m$ 为字符串 s1 的长度， $n$ 为字符串 s2 的长度。