# 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 <= s1.length(); ++i)            f[i][0] = f[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);        for (int i = 1; i <= s2.length(); ++i)            f[0][i] = f[0][i - 1] && s2.charAt(i - 1) == s3.charAt(i - 1);        for (int i = 1; i <= s1.length(); ++i)            for (int j = 1; j <= s2.length(); ++j)                f[i][j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1) && f[i - 1][j])                        || (s2.charAt(j - 1) == s3.charAt(i + j - 1) && f[i][j - 1]);        return f[s1.length()][s2.length()];    }}

### 动规+滚动数组​

// 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 <= s2.length(); ++i)            f[i] = s2.charAt(i - 1) == s3.charAt(i - 1) && f[i - 1];        for (int i = 1; i <= s1.length(); ++i) {            f[0] = s1.charAt(i - 1) == s3.charAt(i - 1) && f[0];            for (int j = 1; j <= s2.length(); ++j)                f[j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1) && f[j])                        || (s2.charAt(j - 1) == s3.charAt(i + j - 1) && f[j - 1]);        }        return f[s2.length()];    }}