leetcode 97. Interleaving String（字符串交错出现） DFS深度优先遍历 + 很明显很经典的DP动态规划做法

桃扇骨 2022-06-08 02:54 154阅读 0赞

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,  
Given:  
s1 = “aabcc”,  
s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true.  
When s3 = “aadbbbaccc”, return false.

**When you see string problem that is about subsequence or matching, dynamic programming method should come to your mind naturally.**

题意很简答，就是问一下字符串可以不可以通过两个字符串交替出现得到。最自觉的方法就是DFS深度优先遍历，但是这个可能会超时（我验证过了，的确会超时）。

一般遇到字符串匹配的问题都应当想到DP动态规划。

参考代码吧，这道题很经典，很值得学习。

代码如下：

/*
     * When you see string problem that is about subsequence or matching, 
     * dynamic programming method should come to your mind naturally. 
     * */
    public class Solution
    {
        public boolean isInterleave(String s1, String s2, String s3) 
        {
            if(s1==null || s2==null || s3==null || s1.length()+s2.length()!=s3.length())
                return false;
    
            //递归超时
            //return Recursive1(s1, s2, s3, 0, 0, 0);
            return byDP(s1,s2,s3);
        }
    
    /*
        *   When you see string problem that is about subsequence or matching, 
        *   dynamic programming method should come to your mind naturally. 
        *   
        *   所以这道题还是用DP的思想解决。大体思路是，s1取一部分s2取一部分，
        *   最后是否能匹配s3。动态规划数组是dp[i][j]，表示：s1取前i位，s2取前j位，
        *   是否能组成s3的前i+j位。初始化是，假设s1为空，那么s2每一位跟s3匹配放入dp[0][j]；
        *   假设s2为空，那么s1每一位跟s3匹配放入dp[i][0]。
        * */
       boolean byDP(String s1, String s2, String s3) 
       {
            boolean [][]dp=new boolean[s1.length()+1][s2.length()+1];
            dp[0][0]=true;
            for(int i=1;i<s1.length()+1;i++)
            {
                if(s1.charAt(i-1)==s3.charAt(i-1) && dp[i-1][0])
                    dp[i][0]=true;
            }
            for(int i=1;i<s2.length()+1;i++)
            {
                if(s2.charAt(i-1)==s3.charAt(i-1) && dp[0][i-1])
                    dp[0][i]=true;
            }
    
            //遍历  DP
            for(int i=1;i<s1.length()+1;i++)
            {
                for(int j=1;j<s2.length()+1;j++)
                {
                    if(s3.charAt(i+j-1)==s1.charAt(i-1) && dp[i-1][j])
                        dp[i][j]=true;
                    if(s3.charAt(i+j-1)==s2.charAt(j-1) && dp[i][j-1])
                        dp[i][j]=true;
                }
            }
            return dp[s1.length()][s2.length()];
        }
    
        //这是递归解法
        boolean Recursive(String s1, String s2, String s3, int i, int j,int k) 
        {
            if(i==s1.length() && j==s2.length() && k==s3.length())
                return true;
            else if( i<s1.length() && s3.charAt(k)==s1.charAt(i) 
                  && j<s2.length() && s3.charAt(k)==s2.charAt(j) )
            {
                if(Recursive(s1, s2, s3, i+1, j, k+1))
                    return true;
                else
                    return Recursive(s1, s2, s3, i, j+1, k+1);
            }
            else if(i<s1.length() && s3.charAt(k)==s1.charAt(i))
                return Recursive(s1, s2, s3, i+1, j, k+1);
            else if(j<s2.length() && s3.charAt(k)==s2.charAt(j))
                return Recursive(s1, s2, s3, i, j+1, k+1);
            else 
                return false;
        }
    }

下面是C++的做做法，

**当你遇到字符串匹配的时候最直觉的方法就是DP动态规划。**

代码如下：

#include<iostream>
    #include <vector>
    
    using namespace std;
    
    //当你遇到字符串匹配的时候一般都要想到DP动态规划的做法
    class Solution 
    {
    public:
        bool isInterleave(string s1, string s2, string s3) 
        {
            if (s3.length() != s1.length() + s2.length())
                return false;
            vector<vector<bool>> dp(s1.length()+1,vector<bool>(s2.length()+1,0));
            dp[0][0] = true;
            for (int i = 1; i <= s1.length(); i++)
            {
                if (s1[i-1] == s3[i-1] && dp[i - 1][0])
                    dp[i][0] = true;
            }
    
            for (int i = 1; i <= s2.length(); i++)
            {
                if (s2[i-1] == s3[i-1] && dp[0][i-1])
                    dp[0][i] = true;
            }
    
            for (int i = 1; i <= s1.length(); i++)
            {
                for (int j = 1; j <= s2.length(); j++)
                {
                    if (s3[i + j - 1] == s1[i - 1] && dp[i - 1][j])
                        dp[i][j] = true;
    
                    if (s3[i + j - 1] == s2[j - 1] && dp[i][j-1])
                        dp[i][j] = true;
                }
            }
            return dp[s1.length()][s2.length()];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 97交错字符串(动态规划)

> 微信搜一搜：`bigsai` > [大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1] > 关注回复进群即可加入力扣打卡群，欢迎划水。近期打卡：

比眉伴天荒/ 2023年01月01日 14:48/ 0 赞/ 141 阅读

相关 Leetcode 97. 交错字符串(DP)

题目重述给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串

喜欢ヅ旅行/ 2022年09月08日 03:44/ 0 赞/ 144 阅读

相关 leetcode 140. Word Break II 深度优先搜索DFS + 很棒的动态规划DP 做法 + 记录前驱节点

Given a non-empty string s and a dictionary wordDict containing a list of non-empty word

妖狐艹你老母/ 2022年06月08日 06:05/ 0 赞/ 175 阅读

相关 leetcode 139. Word Break 深度优先遍历DFS按照index递归搜索 + 很棒的动态规划DP做法

Given a non-empty string s and a dictionary wordDict containing a list of non-empty word

系统管理员/ 2022年06月08日 06:00/ 0 赞/ 174 阅读

相关 leetcode 97. Interleaving String（字符串交错出现） DFS深度优先遍历 + 很明显很经典的DP动态规划做法

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For examp

桃扇骨/ 2022年06月08日 02:54/ 0 赞/ 154 阅读

相关 leetcode 377. Combination Sum IV 组合之和 + DP动态规划 + DFS深度优先遍历

Given an integer array with all positive numbers and no duplicates, find the number of p

淩亂°似流年/ 2022年06月07日 02:50/ 0 赞/ 170 阅读

相关 [Leetcode][python]Interleaving String/交错字符串

题目大意输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交替而成且不改变s1和s2中各个字符原有的相对顺序。解题思路动态规划

矫情吗；*/ 2022年06月06日 08:35/ 0 赞/ 165 阅读

相关 leetcode 416. Partition Equal Subset Sum 动态规划DP + 深度优先遍历DFS

Given a non-empty array containing only positive integers, find if the array can be part

骑猪看日落/ 2022年06月04日 08:18/ 0 赞/ 171 阅读

相关 leetcode 741. Cherry Pickup 来回摘樱桃 + 深度优先遍历DFS + 动态规划DP

In a N x N grid representing a field of cherries, each cell is one of three possible int

分手后的思念是犯贱/ 2022年06月03日 09:54/ 0 赞/ 426 阅读

相关【Leetcode】97. Interleaving String（动态规划）（字符串组合）

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. Example 1

た入场券/ 2022年02月20日 13:41/ 0 赞/ 169 阅读