97. 交错字符串

清疚 2022-10-10 01:56 151阅读 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 条评论，151人围观）

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

相关阅读

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

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

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

相关经典算法面试题：交错字符串

今天的题目是个人非常喜欢的一个，题目的名字叫做“Interleaving String”，这个题目是什么意思呢？理解题意 Interleaving 从字面上讲是交错交

港控/mmm°/ 2022年12月31日 03:27/ 0 赞/ 133 阅读

相关双序列型动态规划——交错字符串

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

梦里梦外;/ 2022年10月27日 12:07/ 0 赞/ 201 阅读

相关 97. 交错字符串

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

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

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

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

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

相关 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 赞/ 161 阅读

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

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

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3

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

相关 LeetCode 97 交错字符串

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

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

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

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

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