博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【leetcode】97. Interleaving String
阅读量:6170 次
发布时间:2019-06-21

本文共 1245 字,大约阅读时间需要 4 分钟。

题目如下:

解题思路:本题可以采用动态规划的方法。记dp[i][j]表示用s1的前i个字符和s2的前j个字符能否组成s3的前(i+j)个字符,如果dp[i-1][j]是True的话,只要s1[i] == s3[i-1+j],那么dp[i][j]就为True;同理,如果dp[i][j-1]是True,只要满足s2[j] == s3[i-1+j],那么dp[i][j]也为True。

代码如下:

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) == 0:            return len(s3) == 0        elif len(s1) == 0:            return s2 == s3        elif len(s2) == 0:            return s1 == s3        elif len(s1) + len(s2) != len(s3):            return False        dp = [ [0]* (len(s2) + 1)  for i in range(len(s1)+1) ]        if s1[0] == s3[0]:            dp[1][0] = 1        if s2[0] == s3[0]:            dp[0][1] = 1        for i in range(len(dp)):            for j in range(len(dp[i])):                if i > 0 and j > 0 and dp[i-1][j] == 0 and dp[i][j-1] == 0:                    dp[i][j] = 0                elif i > 0 and dp[i-1][j] == 1 and s1[i-1] == s3[i-1+j]:                    dp[i][j] = 1                elif j > 0 and dp[i][j-1] == 1 and s2[j-1] == s3[i+j-1]:                    dp[i][j] = 1        #print dp        return dp[-1][-1] == 1

 

转载于:https://www.cnblogs.com/seyjs/p/9556458.html

你可能感兴趣的文章
kettle demo7 从FTP下载多文件类型,解压,插入到数据库
查看>>
我的友情链接
查看>>
我的友情链接
查看>>
iptables 说明及实例
查看>>
vsft 说明及安装
查看>>
ansile(2)模块之copy
查看>>
python 添加自动补全脚本
查看>>
zabbix 3.0.3 安装
查看>>
CentOS学习
查看>>
你不可不知道的NAT
查看>>
Lucene使用IKAnalyzer中文分词笔记
查看>>
从硬盘安装win7操作系统
查看>>
shell监控脚本-监控web server
查看>>
[原创]windows server 2012 AD架构 试验 系列 – 7 ADDB维护
查看>>
如何在Kubernetes中实现容器原地升级
查看>>
S3C6410基于SD卡的裸机开发
查看>>
发博小技巧——如何从项目中剔除第三方组件并在GitHub分享
查看>>
Android动画开发——Animation动画效果
查看>>
使用 Perl 来开发 Nginx 的模块
查看>>
框架Spring.NET之面向切面(AOP)
查看>>