97. 交错字符串

清疚 2022-10-10 01:56 168阅读 0赞

> 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
> 
> 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
> 
> s = s1 + s2 + ... + sn  
> t = t1 + t2 + ... + tm  
> |n - m| <= 1  
> 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...  
> 提示：a + b 意味着字符串 a 和 b 连接。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            /**
            动态规划
            boolean dp[i][j]表示s1的钱i个元素和s2的钱j个元素 可以交替组成s3的前i+j个元素
            dp[i][j]表示s1的钱i个元素和s2的钱j个元素 可以交替组成s3的前i+j个元素条件:
                1如果s1第i个元素和s3的弟i+j个元素相同,那么如果s1的i-1个和s2的j可以组成s3的钱i+j-1个元素 
                OR
                2如果s2第j个元素和s3的弟i+j个元素相同,那么如果s2的j-1个和s1的i可以组成s3的钱i+j-1个元素 
             */
             int m=s1.length();
             int n=s2.length();
             if(m+n!=s3.length()){
                 return false;
             }
             boolean dp[][]=new boolean[m+1][n+1];  
             dp[0][0]=true;  
         
             for(int i=0;i<=m;i++){ //有可能 m ,n 都等于0
                 for(int j=0;j<=n;j++){               
                     if(i>0){
                         dp[i][j]=   (s1.charAt(i-1)==s3.charAt(i+j-1)&&dp[i-1][j]);
                     }
                     if(j>0){
                             //因为i>0时dp[i][j]已经满足了 所以 dp[i][j]||
                       dp[i][j]=    dp[i][j]|| (s2.charAt(j-1)==s3.charAt(i+j-1)&&dp[i][j-1]);
                   
                     }                
                 }
             }
             return dp[m][n];//m-1 n-1的话 可能 m  n 都为空  就越界了  
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/2f782aa4cc374a59b6de418de60d6a4b.png

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

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

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

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

相关 Leetcode 97. 交错字符串

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

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

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

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

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

相关 97. 交错字符串

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

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

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

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

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

相关动态规划：交错字符串

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3

我会带着你远行/ 2022年04月10日 13:41/ 0 赞/ 179 阅读

相关 LeetCode 97 交错字符串

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

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

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

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

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