首页 > 代码库 > Interleaving String
Interleaving String
Given s1, s2, s3, find whethers3 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.
最简单思路就是递归去做,但是这样需要递归最多s3长度的层次,消耗比较大,很容易出现超时错误,进行递归尝试果然出现超时错误,但是递归是解决这个问题最直观的方法。
递归方法不行考虑DP,我们用path[i][j] 记录s1到i 和s2到j 和s3[i+j-1]是否满足要求,这个过程就是填一张二维数组表的过程,先初始化第一行和第一列,然后填表计算出所有,返回path[s1.length][s2.length]的值。
已经AC的代码:
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if(s1.length()+s2.length()!=s3.length()){ return false; } int row = s1.length(); int col = s2.length(); boolean [][]path = new boolean[row+1][col+1]; path[0][0] = true; for(int i=1;i<=row;i++){ path[i][0] = path[i-1][0] && (s1.charAt(i-1)==s3.charAt(i-1)); } for(int i=1;i<=col;i++){ path[0][i] = path[0][i-1] && (s2.charAt(i-1) == s3.charAt(i-1)); } for(int i=1;i<=row;i++){ for(int j=1;j<=col;j++){ path[i][j] = (path[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1)) || (path[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1)); } } return path[row][col]; }}
Interleaving String
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。