⚔ LeetCode | 97. Interleaving String

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Problem

LeetCode 97. Interleaving String

Difficulty : Hard

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Analysis

这一周依然来做一道动态规划的问题，题目要求判断给出的字符串是否是两个字符串的交错组成。很明显，这就是一道动态规划的问题。

Approach 1

对于动态规划的题目，首先，需要先把问题划分为更小的子问题。

这里的问题定义为E(i, j)，表示第一个字符串的前i个字符和第二个字符串的前j个字符是否可以交错形成第三个字符串的前i + j个字符。

而这个问题的答案只有两种成立的可能性：

  • 第一个字符串的第i个字符等于目标字符串的第i + j个字符，并且E(i -1, j)成立，也就是说
    • $S_1(i) == S_3(i + j) && E(i - 1, j)$
  • 第二个字符串的第j个字符等于目标字符串的第i +j个字符，并且E(i, j - 1)成立，也就是说
    • $S_2(i) == S_3(i + j) && E(i , j - 1)$

然后定义最小的子问题，E(i, 0)和E(0, j)

前者代表着第一个字符串的前i个字符都与目标字符串匹配，因此可以简单地表示为

$E(i, 0) = S_1(i) == S_3(i) && E(i - 1, 0)$

后者也是类似的表达方法。

这样，我们就使用动态规划的方法构建出一个$(i + 1) \times (j + 1)$的矩阵

我们来看题目的两个例子：

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
Output: true
1 0 0 0 0 0
1 0 0 0 0 0
1 1 1 1 1 0
0 1 1 0 1 0
0 0 1 1 1 1
0 0 0 1 0 1

我们可以看到矩阵里面有一条从左上角到右下角的标号为 1 的路径，表示存在至少一种的方法可以交错构建出目标字符串

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
Output: false
1 0 0 0 0 0
1 0 0 0 0 0
1 1 1 1 0 0
0 1 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0

这里并不存在路径

最后矩阵的右下角就表示是否可以交错构建出目标字符串。

C++代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
      if (s3.length() != s1.length() + s2.length()) return false;
      bool mat[s1.length() + 1][s2.length() + 1];
      memset(mat, 0, sizeof(mat));
      for (int i = 0; i <= s1.length(); i++) {
        for (int j = 0; j <= s2.length(); j++) {
          if (i == 0 && j == 0) {
            mat[i][j] = true;
          } else if (i == 0) {
            mat[i][j] = mat[i][j - 1] && s2[j - 1] == s3[i + j - 1];
          } else if (j == 0) {
            mat[i][j] = mat[i - 1][j] && s1[i - 1] == s3[i + j - 1];
          } else {
            mat[i][j] = (mat[i][j - 1] && s2[j - 1] == s3[i + j - 1]) || (mat[i - 1][j] && s1[i - 1] == s3[i + j - 1]);
          }
        }
      }
      return mat[s1.length()][s2.length()];
    }
};

这个算法需要遍历两个数组组成的矩阵，时间复杂度为O(nm)，空间复杂度为O(nm``)

n和m分别是两个字符串的长度。

Summary

这是一道非常传统并且经典的动态规划问题，相信只要学过动态规划就很容易可以解决。

土豪通道
0%