这道题目搞了很久。当然是没做出来。然后有挺多衍生问题。
一步步，最后才到这个难度。
Step1,
给你 string s1, string s2, 他们所包含的元素不同。
求出所有的 interleave 并返回。
这用 backtracking 来做。
复杂度应该是 O(2 ^ n)
My code:
public ArrayList<String> findInterleaving(String s1, String s2) {
ArrayList<String> ret = new ArrayList<String>();
helper(s1, 0, s2, 0, "", ret);
return ret;
}
private void helper(String s1, int begin1, String s2, int begin2, String s3, ArrayList<String> ret) {
if (begin1 >= s1.length() && begin2 >= s2.length())
return;
else if (begin1 >= s1.length()) {
s3 += s2.substring(begin2, s2.length());
ret.add(s3);
return;
}
else if (begin2 >= s2.length()) {
s3 += s1.substring(begin1, s1.length());
ret.add(s3);
return;
}
else {
helper(s1, begin1 + 1, s2, begin2, s3 + s1.charAt(begin1), ret);
helper(s1, begin1, s2, begin2 + 1, s3 + s2.charAt(begin2), ret);
}
}
就是设计两个标记位， begin1, begin2
然后每次有两种选择，s1的begin1 位加入到string中，begin1++
或者， s2的begin2 位加入到string中，begin2++
差不多就这样了。
参考网页：
http://www.geeksforgeeks.org/print-all-interleavings-of-given-two-strings/
Step2,
给你三个string, s1, s2, s3, 判断 s3 是否为 s1, s2 的interleave
同时附加一个条件， s1, s2的所有元素，各自互不相同。
My code:
public boolean isInterleaving(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length())
return false;
int i1 = 0;
int i2 = 0;
int i3 = 0;
while (i3 < s3.length()) {
if (i1 < s1.length() && s3.charAt(i3) == s1.charAt(i1))
i1++;
else if (i2 < s2.length() && s3.charAt(i3) == s2.charAt(i2))
i2++;
else
return false;
i3++;
}
return true;
}
那这个就是直接拿 s3 和 s1, s2比较就行了。哪个比上了，就各自向右移动一位。
不难。
参考网页：
http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings/
** Final Step **
去掉那个附加条件。怎么做。
那么会带来一个问题，在某个index处，
s3[i3] == s1[i1] && s3[i3] == s2[i2]
这个时候，选择移动i1, 还是 i2?
答案是，都移动下，
写一个dfs
// A simple recursive function to check whether C is an interleaving of A and B
bool isInterleaved(char *A, char *B, char *C)
{
// Base Case: If all strings are empty
if (!(*A || *B || *C))
return true;
// If C is empty and any of the two strings is not empty
if (*C == '\0')
return false;
// If any of the above mentioned two possibilities is true,
// then return true, otherwise false
return ( (*C == *A) && isInterleaved(A+1, B, C+1))
|| ((*C == *B) && isInterleaved(A, B+1, C+1));
}
显然复杂度会很高， 最坏情况下，
S1 = XXX; S2 = XXX; S3 = XXXXXX
那么复杂度高达 O(2 ^ n)
因为存在了许多重复情况。
所以这个时候，去重复的工具， DP出现了。
其实现在我的大脑已经不太能思考了。
My code:
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length())
return false;
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
if (i == 0 && j == 0) {
dp[i][j] = 1;
continue;
}
char curr = s3.charAt(i + j - 1);
if (i == 0) {
if (curr == s2.charAt(j - 1))
dp[i][j] = dp[i][j - 1];
else
dp[i][j] = 0;
}
else if (j == 0) {
if (curr == s1.charAt(i - 1))
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = 0;
}
else if (curr == s1.charAt(i - 1) && curr != s2.charAt(j - 1))
dp[i][j] = dp[i - 1][j];
else if (curr != s1.charAt(i - 1) && curr == s2.charAt(j - 1))
dp[i][j] = dp[i][j - 1];
else if (curr == s1.charAt(i - 1) && curr == s2.charAt(j - 1))
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] != 0 ? 1 : 0;
}
}
return dp[s1.length()][s2.length()] == 1 ? true : false;
}
}
dp[i][j] 的物理意义：
s1[0, i) and s2[0, j) 的interleave 是否包含 s3[0, i + j)
那么，首先，i = 0, j = 0, 一定包含。
i = 0, j != 0, 表示，当前情况下只有s2进行interleave，那么就是他自己本身。
那就需要判断s2[0, j) 与 s3[0, j) 是否相等。
但因为有dp，即 s2[0, j-1) 与 s3[0, j -1) 的结果已经保存在数组中了直接使用。
所以，只用判断 s2[j - 1] == s3[j - 1]
if yes, then dp[0][j] = dp[0][j - 1];
j = 0 时同样是这个原理。
下面说说最普遍的情况。
i != 0; j != 0
判断 s1[0, i) and s2[0, j) 的interleave 是否包含 s3[0, i + j)
if，
s3[i + j - 1] == s1[j - 1] and s3[i + j - 1] != s2[j - 1]
dp[i][j] = dp[i - 1][j];
if
s3[i + j - 1] != s1[j - 1] and s3[i + j - 1] == s2[j - 1]
dp[i][j] = dp[i][j - 1]
如果都相等的化，那么只要 dp[i - 1][j] and dp[i][j - 1] 中至少有一个是1，它就是 1
DP的思路差不多就这样了。 复杂度是 O(MN)
我觉得我上面的分析很精彩。于是照着分析我自己又敲了一遍。
step 1
My code:
public List<String> interLeaf(String s1, String s2) {
List<String> ret = new ArrayList<String>();
if (s1 == null || s2 == null) {
return ret;
}
helper(s1, s2, 0, 0, "", ret);
return ret;
}
private void helper(String s1, String s2, int begin1, int begin2, String s, List<String> ret) {
if (begin1 >= s1.length()) {
if (begin2 < s2.length()) {
ret.add(s + s2.substring(begin2));
}
}
else if (begin2 >= s2.length()) {
if (begin1 < s1.length()) {
ret.add(s + s1.substring(begin1));
}
}
else {
helper(s1, s2, begin1 + 1, begin2, s + s1.substring(begin1, begin1 + 1), ret);
helper(s1, s2, begin1, begin2 + 1, s + s2.substring(begin2, begin2 + 1), ret);
}
}
step2:
My code：
public boolean simpleMatch(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null) {
return false;
}
if (s1.length() + s2.length() != s3.length()) {
return false;
}
int begin = 0;
int p1 = 0;
int p2 = 0;
while (begin < s3.length()) {
char curr = s3.charAt(begin);
if (p1 < s1.length() && curr == s1.charAt(p1)) {
p1++;
begin++;
}
else if (p2 < s2.length() && curr == s2.charAt(p2)) {
p2++;
begin++;
}
else {
return false;
}
}
return true;
}
Step 3:
public boolean recursiveMatch(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null) {
return false;
}
if (s1.length() + s2.length() != s3.length()) {
return false;
}
return dfs(s1, s2, s3, 0, 0, 0);
}
private boolean dfs(String s1, String s2, String s3, int begin1, int begin2, int begin3) {
if (begin3 == s3.length()) {
return true;
}
else {
if (begin1 >= s1.length() && s2.charAt(begin2) == s3.charAt(begin3)) {
return dfs(s1, s2, s3, begin1, begin2 + 1, begin3 + 1);
}
else if (begin2 >= s2.length() && s1.charAt(begin1) == s3.charAt(begin3)) {
return dfs(s1, s2, s3, begin1 + 1, begin2, begin3 + 1);
}
else if (begin1 < s1.length() && begin2 < s2.length()) {
char c1 = s1.charAt(begin1);
char c2 = s2.charAt(begin2);
char c3 = s3.charAt(begin3);
if (c1 != c2) {
if (c1 == c3) {
return dfs(s1, s2, s3, begin1 + 1, begin2, begin3 + 1);
}
else if (c2 == c3) {
return dfs(s1, s2, s3, begin1, begin2 + 1, begin3 + 1);
}
else {
return false;
}
}
else {
if (c1 == c3) {
return dfs(s1, s2, s3, begin1 + 1, begin2, begin3 + 1)
|| dfs(s1, s2, s3, begin1, begin2 + 1, begin3 + 1);
}
else {
return false;
}
}
}
else {
return false;
}
}
}
然后讲解上说，用这个方法做会有大量的重复。我是真的不知道哪里会存在重复，于是照着逻辑把 recursive tree 画了下来。
假设
S1: xxx
S2: xxx
S3: xxxxxx
(0, 0, 0) 表示三个指针都没开始移动
(1, 0, 1) 表示 s1(0) 与 s3(0) 比较， s2 不动。
以此类推。
然后我画出了这棵树，发现的确存在大量的重复。
比如
(1, 1, 2) 出现了好几次。完全只用计算几次，然后后面的直接拿这个结果就行了。
然后， DP就出来了。自然而然的出来了。
boolean[][] dp = new dp[][];
dp[i][j] ---> (i, j, i + j)
表示， s1 中前i个 与 s2中前j个， 和 s3 中前 i + j 个， 是否匹配。
那么再用上面的方法解答的时候，就可以申明一个全局变量dp[][],
然后计算出结果后就cache进去。
如果miss,那就计算，然后cache进去。
如果hit,那就直接用。
这应该算是 dfs + cut tree
然后讲一下正规的DP做法。
找出递推关系式：
dp[i][j] with dp[i - 1][j] and dp[i][j - 1]
if dp[i - 1][j] == true && s1(i) == s3(i + j):
dp[i][j] = true
else if dp[i][j - 1] == true && s2(j) == s3(i + j):
dp[i][j] = true
以此类推。
My code:
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null ||s2 == null || s3 == null) {
return false;
}
else if (s1.length() + s2.length() != s3.length()) {
return false;
}
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
boolean[][] dp = new boolean[len1 + 1][len2 + 1];
dp[0][0] = true;
for (int i = 0; i < len1; i++) {
if (i < len3 && s1.charAt(i) == s3.charAt(i)) {
dp[i + 1][0] = true;
}
else {
break;
}
}
for (int i = 0; i < len2; i++) {
if (i < len3 && s2.charAt(i) == s3.charAt(i)) {
dp[0][i + 1] = true;
}
else {
break;
}
}
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) { // (i+1, j+1)
if (dp[i][j + 1]) {
if (s1.charAt(i) == s3.charAt(i + j + 1)) {
dp[i + 1][j + 1] = true;
}
}
else if (dp[i + 1][j]) {
if (s2.charAt(j) == s3.charAt(i + j + 1)) {
dp[i + 1][j + 1] = true;
}
}
}
}
return dp[len1][len2];
}
}
总结：
通过这道题目，可以略微看出DP的一个做法。
最关键的不是建立DP模型，而是想出一种递归的做法去求最大值。
俗称为 brute force
然后，画出递归树，分析重复的情况。
为什么会重复？
哪里重复？
然后利用DP，也就是cache来解决这个问题。
这个时候会有两种解决方案。
在原递归算法的基础上，加上这个dp cache
也就是 recursion + cut tree使用纯DP算法，进一步推导出 DP 推导式，初始状态。
然后写出解法。
这应该是DP的正常思路。
Anyway, Good luck, Richardo! -- 08/18/2016
