Finley.Hamilton

# 题目

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()];
}

}
``````

### Finley.Hamilton

Lintcode29 Interleaving String solution 题解

【题目描述】 Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2. 给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。 【题目链接...

coderer
2017/05/07
0
0
Live555源代码解读（4）下

[cpp] view plaincopy static ServerMediaSession* createNewSMS(UsageEnvironment& env,char const* fileName, FILE* /fid/) { // Use the file name extension to determine the type of "......

Sean-x
2016/02/24
19
0
C++11 并发编程教程 - Part 2 : 保护共享数据

2013/12/29
0
0

fbhokzd2jo
2014/04/15
4.6K
0
Ember v2.1.0-beta.4 发布

Ember v2.1.0-beta.4 发布，此版本主要是 bug 修复： #12075 [PERF] Avoid creating a run-loop for events that are unhandled. #12260 [BUGFIX] Ensure is completed before is fired. #1......

oschina
2015/09/14
614
2

15分钟前
0
0
OkHttpClient封装

import java.io.BufferedReader; import java.io.InputStream; import java.io.InputStreamReader; import java.util.Map; import java.util.TreeMap; import java.util.Map.Entry; import o......

16分钟前
1
0

17分钟前
0
0
centos 7 nginx_install.sh

17分钟前
0
0

hansonwong
19分钟前
2
0