剑指 Offer II 096. 字符串交织

Difficulty: 中等

给定三个字符串 s1、s2、s3，请判断 s3 能不能由 s1 和 s2交织（交错） 组成。

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

  • s = s<sub style="display: inline;">1</sub> + s<sub style="display: inline;">2</sub> + ... + s<sub style="display: inline;">n</sub>
  • t = t<sub style="display: inline;">1</sub> + t<sub style="display: inline;">2</sub> + ... + t<sub style="display: inline;">m</sub>
  • |n - m| <= 1
  • 交织 是 s<sub style="display: inline;">1</sub> + t<sub style="display: inline;">1</sub> + s<sub style="display: inline;">2</sub> + t<sub style="display: inline;">2</sub> + s<sub style="display: inline;">3</sub> + t<sub style="display: inline;">3</sub> + ... 或者 t<sub style="display: inline;">1</sub> + s<sub style="display: inline;">1</sub> + t<sub style="display: inline;">2</sub> + s<sub style="display: inline;">2</sub> + t<sub style="display: inline;">3</sub> + s<sub style="display: inline;">3</sub> + ...

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

示例 1：

1
2

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

示例 2：

1
2

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

示例 3：

1
2

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

提示：

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1、s2、和 s3 都由小写英文字母组成

注意：本题与主站 97 题相同：

Solution

Language: ****

 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

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != s1.size() + s2.size()) return false;
        int n = s1.size(), m = s2.size();
        vector<vector<bool>> dp(n+1,vector<bool>(m+1));
        dp[0][0] = true;
        int len3 = n + m;
        // dp[1][0] = s1[0] == s3[0];
        // dp[0][1] = s2[0] == s3[0];
        for(int k=1;k<=len3;++k) {
            for(int i=0;i<=k;++i) {
                int j = k-i;
                if(j<0 || j>m) continue;
                if(i<0 || i>n) continue;
                //合法性校验
                //s1[0..i] + s2[0...j] = s3[0...i+j]
                // if(i && dp[i-1][j] && s1[i] == s3[k-1] ) {
                //     dp[i][j] = true;
                // }
                if(i)  dp[i][j] = dp[i][j] || ( i && dp[i-1][j] && s1[i-1] == s3[k-1] );
                if(j)  dp[i][j] = dp[i][j] || (j && dp[i][j-1] && s2[j-1] == s3[k-1]);
                // if(j && dp[i][j-1] && s2[j] == s3[k-1])
                // {
                //     dp[i][j] = true;
                // }
            }
        }
        return dp[n][m];
    }
};

算法分析

举个例子：

aab = aa + b 【s1出2个， s2出1个】

aab = a + ab 【s1出1个，s2出2个】

aa = a+a 【s1出1个，s2出 1个】

aa = aa + "" 【s1出2个，s2 出 0个】

aabb = aa + b + b

其实就是到达某个状态，然后去暴搜其他状态的空间【向其他状态转换，枚举结果】