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

矫情吗；* 2022-06-06 08:35 167阅读 0赞

## 题目大意 ##

输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交替而成且不改变s1和s2中各个字符原有的相对顺序。

## 解题思路 ##

动态规划，思路容易理解。  
![这里写图片描述][70]  
创建二位数组，然后\[0\]\[0\]是True  
首行首列则是假设其中一个字符串为空时，另一个字符串是否与目标字符串一一对应。  
最后从\[1\]\[1\]开始遍历，拿数字，与目标对应则那个方向的为True。

dp[i][j] = (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])

## 代码 ##

class Solution(object):
        def isInterleave(self, s1, s2, s3):
            """
            :type s1: str
            :type s2: str
            :type s3: str
            :rtype: bool
            """
            if len(s1)+len(s2)!=len(s3): 
                return False
            dp=[[False for i in range(len(s2)+1)] for j in range(len(s1)+1)]
            dp[0][0]=True
            for i in range(1, len(s1)+1):
                dp[i][0] = dp[i-1][0] and s3[i-1]==s1[i-1]  # 边界：之前需要符合并且s1和s3对应位置相同
            for i in range(1, len(s2)+1):
                dp[0][i] = dp[0][i-1] and s3[i-1]==s2[i-1]  # 边界：之前需要符合并且s1和s3对应位置相同
            for i in range(1, len(s1)+1):
                for j in range(1, len(s2)+1):
                    # print i, j, s1[i-1], s3[i+j-1], s2[j-1], s3[i+j-1]
                    dp[i][j] = (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])
    
            # for i in range(len(s1)+1):
            #     print dp[i]
    
            return dp[-1][-1]

## 总结 ##

还可以将而为动态规划压缩至一维，详见：  
[https://shenjie1993.gitbooks.io/leetcode-python/097%20Interleaving%20String.html][https_shenjie1993.gitbooks.io_leetcode-python_097_20Interleaving_20String.html]

[70]: /images/20220606/8f9ceaa619a44fe6a8696b3efe53ac31.png
[https_shenjie1993.gitbooks.io_leetcode-python_097_20Interleaving_20String.html]: https://shenjie1993.gitbooks.io/leetcode-python/097%20Interleaving%20String.html

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

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

给定三个字符串 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][python]Interleaving String/交错字符串

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

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

相关 String字符串

许多知识在我创作的文章 “java变量的两种类型” 里提到了，这里就不赘述类，大家可以参考。 \\ 字符串 \\ 什么是 Java 中的字符串？字符串被作

叁歲伎倆/ 2022年04月23日 07:24/ 0 赞/ 364 阅读

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

![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 阅读