首页 > 其他 > 详细

交叉字符串 · Interleaving String

时间:2018-02-12 12:21:13      阅读:183      评论:0      收藏:0      [点我收藏+]

[抄题]:

给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。(洗牌)

比如 s1 = "aabcc" s2 = "dbbca"

    - 当 s3 = "aadbbcbcac",返回  true.

    - 当 s3 = "aadbbbaccc", 返回 false.

[思维问题]:

  1. 不知道怎么表示交叉。分析要用三维数组,i j k。但是分析j 是否等于i+j,就只用二维数组了。
  2. 不知道为什么看最后一位:第一位不知道是谁出的,但是最后一位非此即彼,可以用来递推。
  3. 不知道状态函数和判断字符函数的关系:二者是要分开的。

[一句话思路]:

[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):

[画图]:

[一刷]:

  1. 行列初始化的规则和普通递归的规则一样,状态函数和判断字符函数都有且分开。
  2. 双序列dp,f[0][0]也要初始化

[二刷]:

[三刷]:

[四刷]:

[五刷]:

  [五分钟肉眼debug的结果]:

[总结]:

[复杂度]:Time complexity: O() Space complexity: O()

[英文数据结构或算法,为什么不用别的数据结构或算法]:

[其他解法]:

[Follow Up]:

[LC给出的题目变变变]:

 [代码风格] :

交叉字符串 · Interleaving String

原文:https://www.cnblogs.com/immiao0319/p/8443848.html

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