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

 [balabala]  像所有题目一样，先从暴力直接法入手，这有助于打开思路，然后再想优化。做题时是明确这题属于DP类题目的，因此就套用DP的思考模式，要求得目标，我需要储备什么信息呢？ 暴力法通常蕴含最本质的思路，即使使用DP技巧也是需要的，这题目最基本的思路就是s3的一个字符要么匹配s1的一个字符，要么匹配s2的，否则可直接判定为false。DP思路通常可以从最后一步来推导递推公式，s3如果确实由s1, s2混插得到，则要么s1[0, n1 - 2] + s2 [0, n2 - 1] = s3[0, n1 + n2 - 1]且s3最后一个字符是s1的最后一个字符，要么s1[0, n1 - 1] + s2 [0, n2 - 2] = s3[0, n1 + n2 - 1]且s3最后一个字符是s2的最后一个字符，如此就可推广到一般情况从而获得递推公式。

 

 

    // Method 2: DP
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length())
            return false;
        int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
        boolean[][] dp = new boolean[n1 + 1][n2 + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n2; j++) {
            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }
        for (int i = 1; i <= n1; i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
            for (int j = 1; j <= n2; j++) {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) 
                    || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        return dp[n1][n2];
    }

    // Method 1: Brute Force
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length())
            return false;
        return recur(s1, s2, s3, 0, 0, 0);
    }
    
    private boolean recur(String s1, String s2, String s3, int p1, int p2, int p3) {
        if (p1 == s1.length() && p2 == s2.length() && p3 == s3.length())
            return true;
        
        if (p1 < s1.length() && s1.charAt(p1) == s3.charAt(p3)) {
            if (recur(s1, s2, s3, p1 + 1, p2, p3 + 1))
                return true;
            else if (p2 < s2.length() && s2.charAt(p2) == s3.charAt(p3))
                return recur(s1, s2, s3, p1, p2 + 1, p3 + 1);
            else
                return false;
        } else if (p2 < s2.length() && s2.charAt(p2) == s3.charAt(p3)) {
            return recur(s1, s2, s3, p1, p2 + 1, p3 + 1);
        } else {
            return false;
        }
    }