多语言详解从「暴搜」到「记忆化搜索」再到「线性 DP（及其进阶）」

宫水三叶的刷题日记

发布于 2023-08-10 08:58:36

3020

发布于 2023-08-10 08:58:36

文章被收录于专栏：宫水三叶的刷题日记

题目描述

这是 LeetCode 上的「97. 交错字符串」，难度为「中等」。

Tag : 「线性 DP」、「记忆化搜索」

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 「交错」 的定义与过程如下，其中每个字符串都会被分割成若干 「非空」 子字符串：

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1

交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

输出：true

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""

输出：true

提示：

0 <= s1.length, s2.length <= 100

0 <= s3.length <= 200

s1、s2、和 s3 都由小写英文字母组成

进阶：您能否仅使用

O(s2.length)

额外的内存空间来解决它?

记忆化搜索

数据范围相比于「暴搜」而言有点大，但将「暴搜」解法作为前置思考，总能为我们带来灵感。

将 s1、s2 和 s3 的长度分别记为

、

和

。

一个显然的情况是若

n + m

不为

，必然不能用 s1 和 s2 来凑成 s3，返回 false。

定义暴搜函数为 boolean dfs(int i, int j)，代表当前处理到 s1 的第

个字符，s2 的第

个字符，能否凑成 s3 的前

i + j

个字符。

最终答案为 dfs(0, 0)。

根据

s1[i]

、

s2[j]

和

s3[i + j]

的关系分情况讨论：

s1[i] = s3[i + j]

，可使用

s1[i]

充当

s3[i + j]

，暴搜

s1[i]

已被使用的情况，决策下一位 dfs(i + 1, j)

s2[j] = s3[i + j]

，可使用

s2[j]

充当

s3[i + j]

，暴搜

s2[j]

已被使用的情况，决策下一位dfs(i, j + 1)

当

i + j = l

时，代表我们成功用 s1 和 s2 凑成了 s3，返回 true；而若在任一回合出现

s1[i] \neq s3[i + j]

且

s2[j] \neq s3[i + j]

，说明构造无法进行，返回 false。

TLE Java 代码：

class Solution {
    char[] cs1, cs2, cs3;
    int n, m, l;
    public boolean isInterleave(String s1, String s2, String s3) {
        cs1 = s1.toCharArray(); cs2 = s2.toCharArray(); cs3 = s3.toCharArray();
        n = s1.length(); m = s2.length(); l = s3.length();
        if (n + m != l) return false;
        return dfs(0, 0);
    }
    boolean dfs(int i, int j) {
        if (i + j == l) return true;
        boolean ans = false;
        if (i < n && cs1[i] == cs3[i + j]) ans |= dfs(i + 1, j);
        if (j < m && cs2[j] == cs3[i + j]) ans |= dfs(i, j + 1);
        return ans;
    }
}

可分析上述 TLE 做法的时间复杂度上界为交错序列个数。

长度分别为

和

形成的交错序列数量为

C(n+m, n) = \frac{(n+m)!}{n! \times m!}

: 从

n + m

个位置中选

个位置按顺序放置 s1，剩下的

个位置唯一确定的放置 s2。

实际上，不同交错序列之间有着相同的前缀（例如 s1 = aac 和 s2 = bbd，具体交错方案中的 aabbcd 和 aabbdc 之间有着相同的前缀 aabb__），可通过「记忆化搜索」来进行减少这些重复的构造。

直接根据 dfs 函数的入参构建缓存器 cache，起始 cache[i][j] = 0；若 cache[i][j] = 1 代表 true；cache[i][j] = -1 代表 false。

如此简单的改动，即可将朴素的 DFS 改成记忆化搜索。

Java 代码：

class Solution {
    char[] cs1, cs2, cs3;
    int n, m, l;
    int[][] cache;
    public boolean isInterleave(String s1, String s2, String s3) {
        cs1 = s1.toCharArray(); cs2 = s2.toCharArray(); cs3 = s3.toCharArray();
        n = s1.length(); m = s2.length(); l = s3.length();
        if (n + m != l) return false;
        cache = new int[n + 10][m + 10];
        return dfs(0, 0);
    }
    boolean dfs(int i, int j) {
        if (cache[i][j] != 0) return cache[i][j] == 1;
        if (i + j == l) return true;
        boolean ans = false;
        if (i < n && cs1[i] == cs3[i + j]) ans |= dfs(i + 1, j);
        if (j < m && cs2[j] == cs3[i + j]) ans |= dfs(i, j + 1);
        cache[i][j] = ans ? 1 : -1;
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.length(), m = s2.length(), l = s3.length();
        if (n + m != l) return false;
        vector<vector<int>> cache(n + 10, vector<int>(m + 10, 0));
        function<bool(int, int)> dfs = [&](int i, int j) {
            if (cache[i][j] != 0) return cache[i][j] == 1;
            if (i + j == l) return true;
            bool ans = false;
            if (i < n && s1[i] == s3[i + j]) ans |= dfs(i + 1, j);
            if (j < m && s2[j] == s3[i + j]) ans |= dfs(i, j + 1);
            cache[i][j] = ans ? 1 : -1;
            return ans;
        };
        return dfs(0, 0);
    }
};

Python 代码：

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m, l = len(s1), len(s2), len(s3)
        if n + m != l:
            return False
        @lru_cache
        def dfs(i, j):
            if i + j == l:
                return True
            ans = False
            if i < n and s1[i] == s3[i + j]:
                ans |= dfs(i + 1, j)
            if j < m and s2[j] == s3[i + j]:
                ans |= dfs(i, j + 1)
            return ans
        return dfs(0, 0)

TypeScript 代码：

function isInterleave(s1: string, s2: string, s3: string): boolean {
    const n = s1.length, m = s2.length, l = s3.length;
    if (n + m !== l) return false;
    const cache = new Array(n + 10).fill(0).map(() => new Array(m + 10).fill(0));
    const dfs = (i: number, j: number): boolean => {
        if (cache[i][j] !== 0) return cache[i][j] === 1;
        if (i + j === l) return true;
        let ans = false;
        if (i < n && s1[i] === s3[i + j]) ans ||= dfs(i + 1, j);
        if (j < m && s2[j] === s3[i + j]) ans ||= dfs(i, j + 1);
        cache[i][j] = ans ? 1 : -1;
        return ans;
    };
    return dfs(0, 0);
};

时间复杂度：共有

n \times m

个状态，复杂度为

O(n \times m)

空间复杂度：

O(n \times m)

线性 DP

直接将「记忆化搜索」中的缓存器修改为我们的动态规划状态定义。

定义

f[i][j]

为使用 s1 的前

个字符，使用 s2 的前

个字符，能否凑出 s3 的前

i + j

个字符。

为了方便，我们令所有字符串的下标均从

开始。

不失一般性，考虑

f[i][j]

如何转移，根据

s1[i]

、

s2[j]

和

s3[i+j]

是否相等进行分析，即 根据当前 s3 的最后一个字符

s3[i + j]

由

s1[i]

和

s2[j]

谁来提供进行讨论 ：

s1[i] = s3[i + j]

：说明当前 s3 的最后一个字符

s3[i + j]

可由

s1[i]

提供，而 s3 此前的

i + j - 1

个字符，可由 s1 的前

i - 1

字符和 s2 的前

个字符共同提供。此时若

f[i - 1][j]

为真，则有

f[i][j]

为真。

s2[j] = s3[i+j]

：说明当前 s3 的最后一个字符串

s3[i+j]

可由

s2[j]

提供，而 s3 此前的

i + j - 1

个字符，可由 s1 的前

字符和 s2 的前

j - 1

个字符共同提供。此时若

f[i][j - 1]

为真，则有

f[i][j]

为真。

综上，只有上述条件任一成立，

f[i][j]

即为真。

一些细节：为了在转移过程中减少边界处理，我们先预处理出

f[0][X]

和

f[X][0]

的状态值（即 s1、s2 和 s3 之间的公共前缀）。

Java 代码：

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(), cs3 = s3.toCharArray();
        int n = s1.length(), m = s2.length(), l = s3.length();
        if (n + m != l) return false;
        boolean[][] f = new boolean[n + 10][m + 10];
        f[0][0] = true;
        for (int i = 1; i <= n && f[i - 1][0]; i++) f[i][0] = cs1[i - 1] == cs3[i - 1];
        for (int i = 1; i <= m && f[0][i - 1]; i++) f[0][i] = cs2[i - 1] == cs3[i - 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i - 1] == cs3[i + j - 1]) f[i][j] |= f[i - 1][j];
                if (cs2[j - 1] == cs3[i + j - 1]) f[i][j] |= f[i][j - 1];
            }
        }
        return f[n][m];
    }
}

Python 代码：

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

C++ 代码：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.length(), m = s2.length(), l = s3.length();
        if (n + m != l) return false;
        vector<vector<bool>> f(n + 10, vector<bool>(m + 10, false));
        f[0][0] = true;
        for (int i = 1; i <= n && f[i - 1][0]; i++) f[i][0] = (s1[i - 1] == s3[i - 1]);
        for (int i = 1; i <= m && f[0][i - 1]; i++) f[0][i] = (s2[i - 1] == s3[i - 1]);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i - 1] == s3[i + j - 1]) f[i][j] = f[i][j] | f[i - 1][j];
                if (s2[j - 1] == s3[i + j - 1]) f[i][j] = f[i][j] | f[i][j - 1];
            }
        }
        return f[n][m];
    }
};

TypeScript 代码：

function isInterleave(s1: string, s2: string, s3: string): boolean {
    const n = s1.length, m = s2.length, l = s3.length;
    if (n + m !== l) return false;
    const f = new Array(n + 10).fill(false).map(() => new Array(m + 10).fill(false));
    f[0][0] = true;
    for (let i = 1; i <= n && f[i - 1][0]; i++) f[i][0] = s1[i - 1] === s3[i - 1];
    for (let i = 1; i <= m && f[0][i - 1]; i++) f[0][i] = s2[i - 1] === s3[i - 1];
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (s1[i - 1] === s3[i + j - 1]) f[i][j] ||= f[i - 1][j];
            if (s2[j - 1] === s3[i + j - 1]) f[i][j] ||= f[i][j - 1];
        }
    }
    return f[n][m];
};

时间复杂度：

O(n \times m)

空间复杂度：

O(n \times m)

进阶

根据状态转移方程可知

f[i][j]

仅依赖于

f[i - 1][j]

和

f[i][j - 1]

，因此可通过「滚动数组」的方式进行优化。

状态定义不变，将动规数组开成

f[2][m + 10]

大小（另外一维的 +10 操作仅为个人习惯）。

随后，当我们需要更新 f[i][X] 时，需要写成 f[i & 1][X]；需要访问 f[i - 1][X] 时，则写成 f[(i - 1) & 1][X] 即可。

最后，同样是为了转移过程中减少边界处理，我们需要使用两个变量 a 和 b 记住 s1 和 s2 与 s3 的公共前缀，并特判掉 s1 或 s2 为空的情况。

Java 代码：

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(), cs3 = s3.toCharArray();
        int n = s1.length(), m = s2.length(), l = s3.length();
        if (n + m != l) return false;
        int a = 0, b = 0;
        while (a < n && cs1[a] == cs3[a]) a++;
        while (b < m && cs2[b] == cs3[b]) b++;
        if (m == 0) return n <= a;
        if (n == 0) return m <= b;
        boolean[][] f = new boolean[2][m + 10];
        f[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                boolean cur = false;
                if (cs1[i - 1] == cs3[i + j - 1]) {
                    if (i == 1) cur |= j <= b;
                    else cur |= f[(i - 1) & 1][j];
                }
                if (cs2[j - 1] == cs3[i + j - 1]) {
                    if (j == 1) cur |= i <= a;
                    else cur |= f[i & 1][j - 1];
                }
                f[i & 1][j] = cur;
            }
        }
        return f[n & 1][m];
    }
}

C++ 代码：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.length(), m = s2.length(), l = s3.length();
        if (n + m != l) return false;
        int a = 0, b = 0;
        while (a < n && s1[a] == s3[a]) a++;
        while (b < m && s2[b] == s3[b]) b++;
        if (n == 0) return m <= b;
        if (m == 0) return n <= a;
        vector<vector<bool>> f(2, vector<bool>(m + 1, false));
        f[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                bool cur = false;
                if (s1[i - 1] == s3[i + j - 1]) {
                    if (i == 1) cur |= j <= b;    
                    else cur |= f[(i - 1) & 1][j];
                }
                if (s2[j - 1] == s3[i + j - 1]) {
                    if (j == 1) cur |= i <= a;
                    else cur |= f[i & 1][j - 1]; 
                }
                f[i & 1][j] = cur;
            }
        }
        return f[n & 1][m];
    }
};

Python 代码：

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m, l = len(s1), len(s2), len(s3)
        if n + m != l:
            return False
        a, b = 0, 0
        while a < n and s1[a] == s3[a]:
            a += 1
        while b < m and s2[b] == s3[b]:
            b += 1
        if m == 0:
            return n <= a
        if n == 0:
            return m <= b
        f = [[False for _ in range(m + 1)] for _ in range(2)]
        f[0][0] = True
        for i in range(1, n+1):
            for j in range(1, m+1):
                cur = False
                if s1[i - 1] == s3[i + j - 1]:
                    if i == 1:
                        cur |= j <= b
                    else:
                        cur |= f[(i - 1) & 1][j]
                if s2[j - 1] == s3[i + j - 1]:
                    if j == 1:
                        cur |= i <= a
                    else:
                        cur |= f[i & 1][j - 1]
                f[i & 1][j] = cur
        return f[n & 1][m]

TypeScript 代码：

function isInterleave(s1: string, s2: string, s3: string): boolean {
    const n = s1.length, m = s2.length, l = s3.length;
    if (n + m !== l) return false;
    let a = 0, b = 0;
    while (a < n && s1[a] === s3[a]) a++;
    while (b < m && s2[b] === s3[b]) b++;
    if (m == 0) return n <= a;
    if (n == 0) return m <= b;
    const f = new Array(2).fill(null).map(() => new Array(m + 1).fill(false));
    f[0][0] = true;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            let cur = false;
            if (s1[i - 1] === s3[i + j - 1]) {
                if (i === 1) cur ||= j <= b;    
                else cur ||= f[(i - 1) & 1][j];
            }
            if (s2[j - 1] === s3[i + j - 1]) {
                if (j === 1) cur ||= i <= a;    
                else cur ||= f[i & 1][j - 1];
            }
            f[i & 1][j] = cur;
        }
    }
    return f[n & 1][m];
};