leetcode 97. 交错字符串

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

看见这个题目第一反应是双指针，但是发现难度是困难，发现事情并不那么简单。然后想的是动态规划，但是动态规划的转移方程真的难想。
假设 dp[i][j] = true 表示 s3字符串的前i+j个字符串可以由s1的前i个字符和s2的前j个字符交错组成。那么由此反推，想要dp[i][j] = true 成立，只有两种可能，就是 dp[i-1][j] = true 成立且字符串s1的第i个字符等于 s3第i+j个字符，或者dp[i][j-1] = true 成立且字符串s2的第j个字符等于 s3第i+j个字符。于是状态转移方程就出来了

// s1[i] 表示字符串s1的第i个字符串，s1[j] 表示字符串s2的第j个字符串
// 之所以都有个减1 是因为字符串的下标从第0开始，
dp[i][j] = (dp[i-1][j] = true 且 s1[i-1] == s3[i+j-1]) 或者 (dp[i][j-1] = true 且 s2[j-1] == s3[i+j-1])

动态规划问题还有个最容易忽略的就是边界条件问题，此题的边界问题需要设置dp[0][0] = true 才行。

public boolean isInterleave(String s1, String s2, String s3) {
        //动态规划
        int m = s1.length();
        int n = s2.length();
       // 如果s1加s2的长度都不等于s3的长度的话，肯定为false
        if(m+n != s3.length()) return false;
        boolean dp[][] = new boolean[m+1][n+1];
        // 边界值
        dp[0][0] = true;
        for(int i =0;i<=m;i++){
            for(int j = 0;j <= n;j++){
                int k = i+j-1;
                if(i > 0){
                    dp[i][j] |= (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(k));
                }

                if(j > 0){
                    dp[i][j] |= (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(k));
                }

            }
        }
        return dp[m][n];
    }

时间复杂度和空间复杂度都是 O(nm)。
执行用时：5 ms, 在所有 Java 提交中击败了57.77%的用户
内存消耗：37.8 MB, 在所有 Java 提交中击败了14.29%的用户

看运行结果应该还是可以有优化的地方，我就看了下题解，发现有大佬用的DFS回溯加记忆化。发现DFS回溯加记忆化实际上还是比动态规划的方程好想。

所谓剪枝就是通过一个二位数组 vis[][]记录以前递归后的结果
vis[][]里面会存储三种值，是为了方便通过其值，进行记忆化的判断后剪枝。
vis[i][j] = 0：表明表明 s1的第i个字符和s2的第j个字符是否与与s3的第i+j个字符匹配这个状态还没递归到
vis[i][j] = -1：表明不管s1的前i-1个字符和s2的前j-1个字符可不可以交错组成s3的前i+j-2个字符，但是反正 s1的第i个字符或者 s2的第j个字符都不与s3的第i+j-1个字符相等，所以剪枝，无需再递归下去这个是剪枝的关键。
vis[i][j] = 1：表明递归成功。

public boolean isInterleave(String s1, String s2, String s3) {

        if (s1.length() + s2.length() != s3.length()) return false;
        int n = s1.length(), m = s2.length();
        /**
         * 所谓剪枝就是通过一个二位数组 vis[][]记录以前递归后的结果
         * vis[][]里面会存储三种值，是为了方便通过其值，进行记忆化的判断后剪枝。
         * vis[i][j] = 0：表明 表明 s1的第i个字符和s2的第j个字符是否与与s3的第i+j个字符匹配这个状态还没递归到
         * vis[i][j] = -1：表明不管s1的前i-1个字符和s2的前j-1个字符可不可以交错组成s3的前i+j-2个字符，但是反正 s1的第i个字符 或者 s2的第j个字符都不与s3的第i+j-1个字符相等，所以剪枝，无需再递归下去这个是剪枝的关键。
         * vis[i][j] = 1：表明 递归成功。
         */
        int[][] vis = new int[n + 1][m + 1];
        return dfs(0, 0, 0, vis, s1, s2, s3);
    }

    //递归+记忆化搜索+剪枝
    public boolean dfs(int i, int j, int k, int[][] vis, String s1, String s2, String s3) {

        //全部匹配成功，返回true
        if (k == s3.length()) {
            vis[i][j] = 1;
            return true;
        }
        
        /**
         * 记忆化判断,剪枝
         * vis[i][j] = -1：表明不管s1的前i-1个字符和s2的前j-1个字符可不可以交错组成s3的前i+j-2个字符，
         * 但是反正 s1的第i个字符 或者 s2的第j个字符都不与s3的第i+j-1个字符相等，所以剪枝，无需再递归下去这个是剪枝的关键。
         */
        if (vis[i][j] == -1) return false;

        if (i < s1.length()) {
            if (s1.charAt(i) == s3.charAt(k)) {
                if (dfs(i + 1, j, k + 1, vis, s1, s2, s3)) {
                    return true;
                }
            }
        }
        if (j < s2.length()) {
            if (s2.charAt(j) == s3.charAt(k)) {
                if (dfs(i, j + 1, k + 1, vis, s1, s2, s3)) {
                    return true;
                }
            }
        }
        //走到这一步说明 s1的第i个字符 或者 s2的第j个字符都不与s3的第i+j-1个字符相等，所以设置vis[i][j] = -1
        vis[i][j] = -1;
        return false;
    }

执行用时：1 ms, 在所有 Java 提交中击败了98.15%的用户
内存消耗：38.2 MB, 在所有 Java 提交中击败了14.29%的用户