首页 > 其他 > 详细

蠡口97. Interleaving String

时间:2019-10-18 14:43:27      阅读:39      评论:0      收藏:0      [点我收藏+]

拿到题,提笔就写分治,结果超时。那很可能需要记录过程,而且这题返回T or F,很像DP。

1)建立矩阵:dp[i][j]表示isTnterleave(s1[0:i], s2[0:j], s3[0:(i+j)])的值,也就是下图中紫色部分是否可以由红色部分和蓝色部分交替拼接组成。dp的初始值全为F

技术分享图片

2)初始化边界:

  dp[0][0]表示isTnterleave("","",""),当然为T;

  当dp[i-1][0]为T(即s3[0:(i-1)]==s1[0:(i-1)])且s3[i-1]==s1[i-1]时,dp[i][0]为T;
  当dp[0][j-1]为T(即s3[0:(j-1)]==s2[0:(j-1)])且s3[j-1]==s2[j-1]时,dp[0][j]为T;

3)建立递推关系:

  当dp[i-1][j]为T且s1[i-1]==s3[i+j-1]时,也就是说i+j-1之前都匹配了,最后一个字符由s1来凑,dp[i][j]为T

  当dp[i][j-1]为T且s2[j-1]==s3[i+j-1]时,也就是说i+j-1之前都匹配了,最后一个字符由s2来凑,dp[i][j]为T

4)返回值:应当返回dp[len(s1)][len(s2)],表示s1的全部和s2的全部是否可以交替拼接组成s3

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s3)!=len(s1)+len(s2): return(False)
        dp=[[False for j in range(len(s2)+1)] for i 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 s1[i-1]==s3[i-1]
        for j in range(1,len(s2)+1): dp[0][j]=dp[0][j-1] and s2[j-1]==s3[j-1]
        for i in range(1,len(s1)+1):
            for j in range(1,len(s2)+1):
                if dp[i-1][j] and s1[i-1]==s3[i+j-1]: dp[i][j]=True
                if dp[i][j-1] and s2[j-1]==s3[i+j-1]: dp[i][j]=True
        return(dp[len(s1)][len(s2)])

 

蠡口97. Interleaving String

原文:https://www.cnblogs.com/Leisgo/p/11697925.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!