链接

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);
// 如果之前计算过