首页 > 代码库 > Interleaving String
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.
方法
二维DP问题,二维矩阵f的大小为:s1.length() * s2.length(); f[i][j] 的状态只和f[i - 1][j] 和 f[i][j - 1]相关。public boolean isInterleave(String s1, String s2, String s3) { int len1 = s1.length(); int len2 = s2.length(); int len3 = s3.length(); if (len1 + len2 != len3) { return false; } boolean[][] f = new boolean[len1 + 1][len2 + 1]; f[0][0] = true; for (int i = 1; i <= len1; i++) { f[i][0] = f[i - 1][0] && s3.charAt(i - 1) == s1.charAt(i - 1); } for (int j = 1; j <= len2; j++) { f[0][j] = f[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1); } for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { int len = i + j; char c1 = s1.charAt(i - 1); char c2 = s2.charAt(j - 1); char c3 = s3.charAt(len - 1); f[i][j] = (c1 == c3 && f[i - 1][j]) || (c2 == c3 && f[i][j - 1]); } } return f[len1][len2]; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。