首页 > 代码库 > leetcode - interleaving string
leetcode - interleaving string
题目描述:
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
那么状态式定义为：
f[ k ] [ i ] [ j ] = ( f [ k-1 ] [i ] [ j - 1] && s2[ j-1] == s3 [ k -1] // s2的第j-1个字符与s3的第k-1个字符匹配。
或者是 = ( f [ k-1 ] [ i-1 ] [ j ] && s1 [ i-1] == s3 [ k -1] // s1的第i-1个字符与s3的第k-1个字符匹配。
两者只要有一个满足条件即可。
代码如下：
Version 1: 时间复杂度 O(n^3)，空间复杂度 O(n^3).Time ： ~200ms
<script src="https://code.csdn.net/snippets/423429.js" type="text/javascript"></script>
Version 2: 时间复杂度 O(n^2)，空间复杂度 O(n^2).Time ：~ 4ms
<script src="https://code.csdn.net/snippets/423430.js" type="text/javascript"></script>
Version 3: 时间复杂度 O(n^2)，空间复杂度 O(n). Time ：~ 4ms
使用滚动数组来解决：
<script src="https://code.csdn.net/snippets/423433.js" type="text/javascript"></script>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。