LeetCode097——交错字符串
我的LeetCode代码仓：https://github.com/617076674/LeetCode
原题链接：https://leetcode-cn.com/problems/interleaving-string/description/
题目描述：
知识点：动态规划、递归
思路一：递归实现（在LeetCode中提交会超时）
本题的思路其实很清晰，就是依次删去s3中在s1中出现的字符。
需要注意的是，删是按顺序地删。即对于s1 = "ab"，s2 = "bc"，s3 = "bbac"的情况，如果不考虑s1中"a"和"b"的相对位置，那么其结果就变成了true。而这个例子的结果明显是false。我们在删除的"b"的时候，应该从s3中被删除掉的"a"的那个位置之后去寻找"b"，这样删除的"ab"才是真正的s1，不会对这种情形进行误判。因此，在递归的时候，我们需要传入一个额外的参数index，它记录的是上一次删除的字符的位置。我们下一个删除的字符在s3中的位置必须大于等于index值。
递归终止条件：
（1）如果s1加上s2的长度和s3的长度不相等，即返回false。
（2）如果s1的长度为0，比较字符串s2是否与字符串s3相等，相等则返回true，不相等则返回false。
递归过程：
（1）从s3中index位置开始寻找与s1中第一个字符相同的字符，用一个ArrayList<Integer>型变量arrayList记录其位置。
（2）对于arrayList中的每一个位置，我们都尝试删除，并递归调用该函数来判断是否s3删除对应字符后的字符串是否右s1中除了第一个字符外的子串和s2交错组成。只要有任何一个位置返回的结果是true，就直接返回true。否则，返回false。
时间复杂度是O(n * m)，其中n为字符串s1的长度，m为字符串s3的长度。空间复杂度即递归深度，是O(n)。
JAVA代码：
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
return isInterleave(s1, s2, s3, 0);
}
private boolean isInterleave(String s1, String s2, String s3, int index){
int n1 = s1.length();
int n2 = s2.length();
int n3 = s3.length();
if(n1 + n2 != n3){
return false;
}
if(s1.length() == 0){
return s2.equals(s3);
}
ArrayList<Integer> arrayList = new ArrayList<>();
for(int i = index; i < n3; i++){
if(s1.charAt(0) == s3.charAt(i)){
arrayList.add(i);
}
}
for (int i = 0; i < arrayList.size(); i++) {
if(isInterleave(s1.substring(1), s2, s3.substring(0, arrayList.get(i)) + s3.substring(arrayList.get(i) + 1), arrayList.get(i))){
return true;
}
}
return false;
}
}
思路二：动态规划
状态定义：
f(x, y) -------- s1中[0, x - 1]区间的子串和s2中[0, y - 1]区间的子串能否构成s3中[0, x + y - 1]区间的子串。
状态转移：
（1）当x == 0时，说明此时s1中[0, x - 1]区间的子串是一个空串。只需根据s2中[0, y - 1]区间的子串和s3中[0, y - 1]区间的子串判断即可。
（2）当y == 0时，说明此时s2中[0, y - 1]区间的子串是一个空串。只需根据s1中[0, x - 1]区间的子串和s3中[0, x - 1]区间的子串判断即可。
（3）当x != 0且y != 0时，分为两种情况
a：如果f(x - 1, y) == true，即s1中[0, x - 2]区间的子串能够和s2中[0, y - 1]区间的子串构成s3中[0, x + y - 2]区间的子串且s1.charAt(x - 1) == s3.charAt(x + y - 1)，显然f(x, y)值为true。
b：如果f(x, y - 1) == true，即s1中[0, x - 1]区间的子串能够和s2中[0, y - 2]区间的子串构成s3中[0, x + y - 2]区间的子串且s2.charAt(y - 1) == s3.charAt(x + y - 1)，显然f(x, y)值为true。
时间复杂度和空间复杂度均是O(n * m)，其中n为字符串s1的长度，m为字符串s2的长度。
JAVA代码：
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int n1 = s1.length();
int n2 = s2.length();
int n3 = s3.length();
if(n1 + n2 != n3){
return false;
}
boolean[][] flags = new boolean[n1 + 1][n2 + 1];
flags[0][0] = true;
for (int i = 1; i < n1 + 1; i++) {
if(!flags[i - 1][0] || s1.charAt(i - 1) != s3.charAt(i - 1)){
break;
}
flags[i][0] = true;
}
for(int i = 1; i < n2 + 1; i++){
if(!flags[0][i - 1] || s2.charAt(i - 1) != s3.charAt(i - 1)){
break;
}
flags[0][i] = true;
}
for (int i = 1; i < n1 + 1; i++) {
for (int j = 1; j < n2 + 1; j++) {
if(flags[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)){
flags[i][j] = true;
continue;
}
if(flags[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)){
flags[i][j] = true;
}
}
}
return flags[n1][n2];
}
}
LeetCode解题报告：