97. Interleaving String

Posted on | In | 浏览 次
Words count in article: 703 | Reading time ≈ 3

题目

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

Example 1:

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

Example 2:

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

解题思路

  • 这道题目的意思比较简单，给出三个字符串s1,s2,s3，问字符串s3是否由字符串s1和字符串s2交错而成的，返回真假即可。接下来我将会介绍以下几种解决的思路。
  • 思路
    • 动态规划问题需要先找到子问题，然后子问题递推得到问题的解决。本题我们可以将问题看成字符串s1的前i个字符与s2的前j个字符是否能交错生成s3的前i+j-2个字符。确认子问题后，我们需要找到其中的转移方程。
    • 维护一个二维的布尔数组dp[s1.size][s2.size]，，用dp[i][j]表示字符串s1的前i个字符即与字符串s2的前j个字符是否可以交错生成字符串s3的前i+j-2个字符的匹配情况。假如dp[i][j]为true，即表示字符串s3的前i+j-2个字符由字符串s1的前i个字符即与字符串s2的前j个字符交错生成，否则表示不可以。
    • 对于dp[i][j]的表示，我们可以列出以下几种情况
      • i = j = 0
        • 空对空，肯定匹配。
        • dp[i][j] = true
      • i != 0 && j = 0
        • 此时可以看成s1的前i个字符串与s3的前i个字符串的匹配情况。
        • dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1])
      • i = 0 && j != 0
        • 此时可以看成s2的前j个字符串与s3的前j个字符串的匹配情况。
        • dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1])
      • i > 0 && j > 0
        • 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]匹配的情况，我们需要将二者得到的匹配情况进行或操作来得到dp[i][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])

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// dp
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size())	return false;
        bool dp[s1.size() + 1][s2.size() + 1];
        dp[0][0] = true;

        for(int i = 1; i <= s1.size(); ++i)
            dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1]);

        for(int j = 1; j <= s2.size(); ++j)
            dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1]);

        for(int i = 1; i <= s1.size(); ++i) {
            for(int j = 1; j <= s2.size(); ++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[s1.size()][s2.size()];
    }
};