（难度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.

### 样例

Example 1:

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

Example 2:

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

### 题解

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);
}
};

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