8d11df6582a13bafd82483c140af1def
(难度Hard)Problem 97. Interleaving String(插入字符串)

链接

Interleaving String - LeetCode

难度等级

Hard

题干

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

题意

给定三个字符串,s1,s2,和s3,要求s3是不是s1和s2两个字符串字符交错而生成的。

样例

Example 1:

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

Example 2:

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

题解

拿到题的第一反应是,这题怎么这么简单,我们只需要把s3当中的字符按位匹配,然后判断一下,是否都匹配完成不就好了吗?这是一个$O(n)$的算法而已。

但是当我仔细一分析,发现不是这么回事,因为s1和s2当中的元素是存在重复的。当出现重复的时候,当下的选择会干扰到以后的结果。所以,要想得到正确答案,我们需要搜索所有的情况。很容易想到,这是一个递归的搜索。

当下无非两种情况,要么和s1匹配, 要么和s2匹配。如果都能匹配,那么则分别尝试。

Code很好写,只有短短几行,如下:

class Solution {
public:
      // a,b,c分别表示s1,s2,和s3已经匹配的长度
    bool dfs(string &s1, string & s2, string & s3, int a, int b, int c, int l1, int l2 ,int l3) {
        if (c == l3) return true;
        bool flag = false;
          // 分别判断和s1以及s2匹配的情况,只要匹配成功就return true
        if (a < l1 && s1[a] == s3[c]) flag |= dfs(s1, s2, s3, a+1, b, c+1, l1, l2, l3);
        if (b < l2 && s2[b] == s3[c]) flag |= dfs(s1, s2, s3, a, b+1, c+1, l1, l2, l3);
        return flag;
    }

    bool isInterleave(string s1, string s2, string s3) {
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();
        if (l3 != l1 + l2) return false;
        return dfs(s1, s2, s3, 0, 0, 0, l1, l2, l3);
    }
};

虽然样例能过,但是很遗憾,这样提交是不行的,会因为可能性过多而超时。

我们分析一下超时的原因,其实很简单,就和我们每一次搜索问题的超时是一样的。一个是可能性太多了,尤其是字符出现大量相同的时候。还有一种情况是我们做了很多冗余的判断。

最简单的解决办法就是我们用一个map把递归过程当中出现的状态都记录下来,当我们第二次遇到的时候,如果已经出现过了,则直接返回。这样可以大大节省递归产生的冗余。

代码:

```
class Solution {
public:
// buffer存储中间结果
map, bool> mp;
bool dfs(string &s1, string & s2, string & s3, int a, int b, int c, int l1, int l2 ,int l3) {
// 用a和b来表示状态
pair pr = pair (a, b);
// 如果之前计算过

top Created with Sketch.