## 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.

### 分析

f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j])
|| (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]);


### 递归

// Interleaving String
// 递归，会超时，仅用来帮助理解
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length())
return false;
if (s1.isEmpty() || s2.isEmpty()) return true;

return isInterleave(s1, 0, s1.length(),
s2, 0, s2.length(), s3, 0, s3.length());
}

private static boolean isInterleave(String s1, int begin1, int end1,
String s2, int begin2, int end2,
String s3, int begin3, int end3) {
if (begin3 == end3)
return begin1 == end1 && begin2 == end2;

return (begin1 < end1 && s1.charAt(begin1) == s3.charAt(begin3) &&
isInterleave(s1, begin1 + 1, end1, s2, begin2, end2,
s3, begin3 + 1, end3)) ||
(begin2 < end2 && s2.charAt(begin2) == s3.charAt(begin3) &&
isInterleave(s1, begin1, end1,
s2, begin2 + 1, end2, s3, begin3 + 1, end3));
}
}

### 动规

// Interleaving String
// 二维动规，时间复杂度O(n^2)，空间复杂度O(n^2)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length())
return false;

boolean[][] f = new boolean[s1.length() + 1][s2.length() + 1];
for (int i = 0; i < s1.length() + 1; ++i)
Arrays.fill(f[i], true);

for (int i = 1; i 

### 动规+滚动数组

// Interleaving String
// 二维动规+滚动数组，时间复杂度O(n^2)，空间复杂度O(n)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length())
return false;

if (s1.length() < s2.length())
return isInterleave(s2, s1, s3);

boolean[] f = new boolean[s2.length() + 1];
Arrays.fill(f, true);

for (int i = 1; i