Keshawn_lu's Blog

Leetcode 97. 交错字符串

字数统计: 410阅读时长: 2 min
2020/07/18 Share

题目简介:

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1s2 交错组成的。

示例 1:

1
2
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

1
2
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

思路:

动态规划,dp[i][j]代表s1的前i个字符和s2的前j个字符能否构成s3的前i + j个字符。

初始化dp[0][0] = true

dp[i][j]存在两种情况的判定:

  1. s1[i - 1] == s3[i + j - 1],即s1的第i个字符等于s3的第i + j个字符,此时dp[i][j]取决于s1的前i - 1个字符与s2的前j个字符能否构成s3的前i + j - 1个字符,即dp[i][j] = dp[i - 1][j]
  2. s2[j - 1] == s3[i + j - 1],即s2的第j个字符等于s3的第i + j个字符,此时dp[i][j]取决于s1的前i个字符与s2的前j - 1个字符能否构成s3的前i + j - 1个字符,即dp[i][j] = dp[i][j - 1]

最后返回dp[s1.size()][s2.size()]即可。

代码如下:

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
32
33
34
35
36
37
38
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {

if(s1.size() + s2.size() != s3.size()) //长度不同,直接返回false
return false;

vector<vector<bool>> dp(s1.size() + 1, vector<bool>(s2.size() + 1, false));

dp[0][0] = true; //s1的前i个和s2的前j个能否组成s3

for(int i = 0; i <= s1.size(); i++){

for(int j = 0; j <= s2.size(); j++){

if(i > 0){

if(s1[i - 1] == s3[i + j - 1]){

if(dp[i - 1][j])
dp[i][j] = true;
}
}

if(j > 0){

if(s2[j - 1] == s3[i + j - 1]){

if(dp[i][j - 1])
dp[i][j] = true;
}
}

}
}
return dp[s1.size()][s2.size()];
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: