首页 > 代码库 > 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.
分析
- 最直观的当然是递归了
- 因为是两个变量,二维矩阵是少不了的
- d[i][j]可以表达,当s1取前i个,s2取前j个,是否可以组成s3取前i+j个?
- 编程上面有技巧,不能让d[s1.length][s2.length],这样index只能取到s1.length-1和s2.length-1
- 推导公式,关键就在s1[i-1]==s3[i+j-1]这一句,因为是取s1的前i个,那最后一个就是s[i-1]了,这一点要严格按照d[i][j]的定义来
d[i][j] = (d[i-1][j]&&s1[i -1 ]==s3[i+j -1 ]) || (d[i][j-1]&&s2[j-1]==s3[i+j-1])
代码
package InterleaveString; public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if (s1.length() + s2.length() != s3.length()) { return false; } boolean[][] d = new boolean[s1.length()+1][s2.length()+1]; d[0][0] = true; for (int i = 1; i <= s1.length(); i++) { if(s1.charAt(i-1) == s3.charAt(i-1)) { d[i][0] = true; } else { break; } } for (int j = 1; j <= s2.length(); j++) { if (s2.charAt(j-1) == s3.charAt(j-1)) { d[0][j] = true; } else { break; } } for (int i = 1; i <= s1.length(); i++) { for (int j = 1; j <= s2.length(); j++) { d[i][j] |= d[i - 1][j] && s1.charAt(i-1) == s3.charAt(i + j-1); d[i][j] |= d[i][j - 1] && s2.charAt(j-1) == s3.charAt(i + j-1); } } return d[s1.length()][s2.length()]; } }
Interleaving String
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。