题目链接：https://leetcode-cn.com/problems/interleaving-string/

题目描述：

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

思考：

这道题可以采用动态规划去解决，通过列举观察可以得出状态转移方程伪代码:

if(s1[i] == s3[i + j]){
  f[i][j] = f[i-1][j] 
}
if(s2[i] == s3[i + j]){
  f[i][j]=f[i][j-1] 
}

踩到的坑：

开始想着用递归方式去解决，可无奈时间复杂度太高，提交后显示超时，不得不采用前溯去处理。

实现：

递归实现：

public static boolean isInterleave(String s1, String s2, String s3) {
        if ((s1.length() + s2.length()) != s3.length()) {
            return false;
        }
        if (s1.length() == 0 && s2.length() == 0){
            return true;
        }
        if (s1.length() == 0 || s2.length() == 0){
            if (s3.equals(s1 + s2)){
                return true;
            } else {
                return false;
            }
        }
        Boolean condiction1 = s1.substring(s1.length() - 1).equals(s3.substring(s3.length()-1));
        Boolean condiction2= s2.substring(s2.length() - 1).equals(s3.substring(s3.length()-1));
        if (condiction2 && condiction1){
            if (isInterleave(s1, s2.substring(0, s2.length() - 1), s3.substring(0, s3.length()-1)) || isInterleave(s1.substring(0, s1.length() - 1), s2, s3.substring(0, s3.length()-1))){
                return true;
            } else {
                return false;
            }
        } else if(condiction1 && !condiction2){
            return isInterleave(s1.substring(0, s1.length() - 1), s2, s3.substring(0, s3.length()-1));
        } else if(!condiction1 && condiction2){
            return isInterleave(s1, s2.substring(0, s2.length() - 1), s3.substring(0, s3.length()-1));
        }
        return false;
    }

非递归实现：

 public static boolean isInterleave0(String s1, String s2, String s3){
        int m = s1.length();
        int n = s2.length();
        int s = s3.length();
        if ((m + n) != s){
            return false;
        }
        boolean[][] f = new boolean[m+1][n+1];
        f[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i > 0){
                    f[i][j] = f[i][j] || ((f[i - 1][j] && (s1.charAt(i-1) == s3.charAt(i + j - 1))));
                }
                if (j > 0){
                    f[i][j] = f[i][j] || ((f[i][j - 1] && (s2.charAt(j-1) == s3.charAt(i + j - 1))));
                }
            }
        }
        return f[m][n];
    }