[DP]97. Interleaving String

  • 分类:DP
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n^2)

97. Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

代码:

class Solution:
    def isInterleave(self, s1: 'str', s2: 'str', s3: 'str') -> 'bool':

        #判断边界条件
        if s1==None and s2==None and s3==None:
            return True
        if s1==None or s2==None or s3==None:
            return False
        if len(s1)+len(s2)!=len(s3):
            return False

        dp=[[False for i in range(len(s2)+1)] for i in range(len(s1)+1)]
        dp[0][0]=True

        for i in range(1,len(s3)+1):
            lens1=0
            while lens1<=i and lens1<=len(s1):
                lens2=i-lens1
                if lens2>len(s2):
                    lens1=i-len(s2)
                    continue
                if (lens2>0 and s3[i-1]==s2[lens2-1] and dp[lens1][lens2-1]) or \
                   (lens1>0 and s3[i-1]==s1[lens1-1] and dp[lens1-1][lens2]):
                    dp[lens1][lens2]=True
                lens1+=1


        return dp[-1][-1]

讨论:

1.计数题和True/False的题目都要考虑用DP做
2.DP有四个要素

  • state状态,这里是true or false
  • init初始条件
  • function,这个最重要
  • result给出的结果
  1. 这里的转移方程是当s3最后一个字符等于s2最后一个字符的时候且dp[lens1][lens2-1]==True的时候,dp[lens1][lens2]==True
    4.在lens2>len(s2)的时候,为了加快进度,lens1=i-len(s2)可以加个速
    5.但好像DP本身就不快???
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 8,660评论 0 18
  • 本文是我自己在秋招复习时的读书笔记,整理的知识点,也是为了防止忘记,尊重劳动成果,转载注明出处哦!如果你也喜欢,那...
    波波波先森阅读 4,342评论 1 6
  • 前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。如何从这篇文章受益...
    落影loyinglin阅读 4,556评论 2 12
  • 分治方法 将问题划分成互不相交的子问题 递归地求解子问题 将子问题的解组合起来 动态规划(两个要素:最优子结构、子...
    superlj666阅读 3,468评论 0 0
  • 时间是明末清初某一个落寞的年代,正逢腊月初雪,却也年关将近了。六角晶莹棱角分明的雪花,大片大片铺满了吴宅屋檐上已然...
    流烟远逝阅读 3,247评论 0 2