Keshawn_lu's Blog

Leetcode 97. 交错字符串

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

题目简介：

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

示例 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. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网