(难度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);
// 如果之前计算过
链接
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);
// 如果之前计算过
链接
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);
// 如果之前计算过