LeetCode-T97-交错字符串（interleaving-string）

小灰灰 2023-02-28 01:57 26阅读 0赞

# 题目 #

[原题链接][Link 1]

### 题目描述： ###

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

### 样例 ###

#### case1: ####

输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”  
输出: true

#### case2: ####

输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”  
输出: false

# 题解 #

### 思路 ###

考虑动态规划，既：s1的前i个字符和s2的前j个字符能否组成s3的前k个字符  
对于s3中的前k个字符，考虑第k个字符是从s1的第i个字符而来，还是从s2的第j个字符而来。  
我们能明确的是只有当 i+j == k 时才有可能组合成，s3的第k个字符只有和s1的第i个字符相等才能从它而来，s2中亦如此  
所以我们考虑 dp\[i\]\[j\] 表示为s1的前i个字符和s2的前j个字符能否组成s3的前k（k == i+j）个字符  
因此我们可以推断出动态转译方程为 ：  
当 s3\[i+j\] == s1\[i\] && s3\[i+j\] != s2\[j\]时 dp\[i\]\[j\] = dp\[i-1\]\[j\]  
当 s3\[i+j\] == s2\[j\] && s3\[i+j\] != s1\[i\] 时 dp\[i\]\[j\] = dp\[i\]\[j-1\]  
当 s3\[i+j\] == s1\[i\] && s3\[i+j\] == s2\[j\] 时 dp\[i\]\[j\] = dp\[i-1\]\[j\] | dp\[i\]\[j-1\]  
当 s3\[i+j\] != s1\[i\] && s3\[i+j\] != s2\[j\] dp\[i\]\[j\] = false  
我们可以发现 dp\[i\]\[j\] 只和 dp\[i-1\]\[j\] / dp\[i\]\[j-1\] 有关 ，因此我们可以化二维为一维 dp\[j\]

### 代码 ###

/** * https://leetcode-cn.com/problems/interleaving-string/ * 思路： * 考虑动态规划，既：s1的前i个字符和s2的前j个字符能否组成s3的前k个字符 * 对于s3中的前k个字符，考虑第k个字符是从s1的第i个字符而来，还是从s2的第j个字符而来。 * 我们能明确的是只有当 i+j == k 时才有可能组合成，s3的第k个字符只有和s1的第i个字符相等才能从它而来，s2中亦如此 * 所以我们考虑 dp[i][j] 表示为s1的前i个字符和s2的前j个字符能否组成s3的前k（k == i+j）个字符 * 因此我们可以推断出动态转译方程为 ： 当 s3[i+j] == s1[i] && s3[i+j] != s2[j]时 dp[i][j] = dp[i-1][j] * 当 s3[i+j] == s2[j] && s3[i+j] != s1[i] 时 dp[i][j] = dp[i][j-1] * 当 s3[i+j] == s1[i] && s3[i+j] == s2[j] 时 dp[i][j] = dp[i-1][j] | dp[i][j-1] * 当 s3[i+j] != s1[i] && s3[i+j] != s2[j] dp[i][j] = false * 我们可以发现 dp[i][j] 只和 dp[i-1][j] / dp[i][j-1] 有关 ，因此我们可以化二维为一维 dp[j] * * @author yingxiang */
    public class LeetCode_97 { 
    
      boolean[] dp;
    
      int n,m,k;
    
      public boolean isInterleave(String s1, String s2, String s3) { 
        n = s1.length();
        m = s2.length();
        k = s3.length();
        if(n + m != k) { 
          return false;
        }
        dp = new boolean[m+1];
        for(int i = 0; i <= n; i++) { 
          for(int j = 0; j <= m ; j++) { 
            boolean flag = false;
            if(i == 0 && j == 0) { 
              dp[0] = true;
              continue;
            }
    
            if(i != 0 && s3.charAt(i+j-1) == s1.charAt(i - 1)) { 
              flag = true;
            }
    
            if(j != 0 && s3.charAt(i+j-1) == s2.charAt(j - 1)) { 
    
              if(flag) { 
                dp[j] = dp[j-1] | dp[j];
              } else { 
                dp[j] = dp[j - 1];
              }
    
              flag = true;
            }
    
            if(flag == false) { 
              dp[j] = false;
            }
          }
        }
        return dp[m];
      }
    
      public static void main(String[] args) { 
        String s1 = "ab";
        String s2 = "bc";
        String s3 = "babc";
        System.out.println(new LeetCode_97().isInterleave(s1, s2, s3));
      }
    }

[Link 1]: https://leetcode-cn.com/problems/interleaving-string/

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode_动态规划_中等_97.交错字符串

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交

待我称王封你为后i/ 2023年10月06日 23:42/ 0 赞/ 35 阅读

相关 leetcode 97交错的字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。示例 1: 输入: s1 = “aabcc”, s2 = “dbbca”, s3

墨蓝/ 2023年06月20日 06:14/ 0 赞/ 14 阅读

相关 LeetCode-T97-交错字符串（interleaving-string）

题目 [原题链接][Link 1] 题目描述：给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。样例 cas

小灰灰/ 2023年02月28日 01:57/ 0 赞/ 27 阅读

相关 LeetCode_97.交错字符串_没懂

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

港控/mmm°/ 2023年02月27日 13:48/ 0 赞/ 28 阅读

相关 Leetcode 97. 交错字符串

Leetcode 97. 交错字符串 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.c

梦里梦外;/ 2023年02月11日 10:20/ 0 赞/ 38 阅读

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

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

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

相关 97. 交错字符串

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

清疚/ 2022年10月10日 01:56/ 0 赞/ 180 阅读

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

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

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

相关 LeetCode 97 交错字符串

题目：给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。输入输出：输入: s1 = "aabcc", s2 = "d

ゞ浴缸里的玫瑰/ 2022年03月06日 15:12/ 0 赞/ 222 阅读

相关 leetcode：97. 交错字符串（java 回溯）

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。示例 1: 输入: s1 = "aabcc", s2 = "

r囧r小猫/ 2021年09月28日 09:56/ 0 赞/ 273 阅读