LC97. 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.
初步的想法是记录每一步可能match的位置，然后backtrack，然后递归… 天啊求实习啊。看了眼discuss 非常简洁的dfs方法, 记录两个字符串匹配到的位置，用带memo的DP存每一步匹配的结果。
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
char[] arr1 = s1.toCharArray();
char[] arr2 = s2.toCharArray();
char[] arr3 = s3.toCharArray();
if(arr3.length != arr1.length + arr2.length) return false;
return isValid(arr1, arr2, arr3, 0, 0, 0, new boolean[arr1.length+1][arr2.length+1]);
}
// i - c1 pos, j - c2 pos, k - c3 pos
// inValid[i][j] cache whether s1[0-i] and s2[0-j] can interleave s3[0-k]
private boolean isValid(char[] c1, char[] c2, char[] c3, int i, int j, int k, boolean[][] inValid){
if(inValid[i][j]) return false;
if(k == c3.length) return true;
boolean valid = (i < c1.length && c1[i] == c3[k] && isValid(c1, c2, c3, i+1, j, k+1, inValid))
|| (j < c2.length && c2[j] == c3[k] && isValid(c1, c2, c3, i, j+1, k+1, inValid));
if(!valid) inValid[i][j] = true;
return valid;
}
}
O(m+n), O(mn)大概?
膜拜答主，如此简洁的答案，比我写的bug不知道好了多少…