剑指 Offer II 096. 字符串交织

剑指 Offer II 096. 字符串交织【中等题】

思路：【动态规划】

二阶dp数组更好理解一点，但没有一阶dp数组快，数组定义、边界条件、转移方程等详见代码注释。

代码：

二阶

class Solution {
    
    public boolean isInterleave(String s1, String s2, String s3) {
    
        //求出字符串 s1 s2 的长度为 m n
        int m = s1.length(),n = s2.length();
        //如果 m + n != 字符串s3的长度，那么s1和s2必不可能交织成s3
        if (m + n != s3.length()){
    
            return false;
        }
        //定义 dp 数组，dp[i][j] 表示字符串s1的前i个字符 与 字符串s2的前j个字符 能否通过交织得到s3的前i+j个字符 即 能够得到s3的子串[0,i+j)
        boolean[][] dp = new boolean[m+1][n+1];
        //边界条件 dp[0][0] = true 因为空串与空串交织，必然能够得到空串 
        dp[0][0] = true;
        //遍历字符串s1和s2，判断s1的前i个字符和s2的前j个字符是否能交织成s3的[0,i+j)子串
        for (int i = 0; i <= m; i++) {
    
            //说明 i 和 j 从 0 开始，因为字符串交织规则上没有提到必须两个字符串都得贡献字符
            for (int j = 0; j <= n; j++) {
    
                //s3的目标子串边界
                int p = i+j-1;
                //i > 0 表示一定选择s1中字符进行字符串交织
                if (i > 0){
    
                    //转移方程如下，表示 当s1的第i个字符与s3的第i+j个字符相等时，交织方向为 s2 - s1 -> s3
                    //此时 dp[i][j]能否交织成功，取决于 dp[i-1][j]能否交织成功
                    dp[i][j] = dp[i][j] || (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(p));
                }
                //j > 0 表示一定选择s2中字符进行字符串交织
                if (j > 0){
    
                    //转移方程如下，表示 当s2的第j个字符与s3的第i+j个字符相等时，交织方向为 s1 - s2 -> s3
                    //此时 dp[i][j]能否交织成功，取决于 dp[i][j-1]能否交织成功
                    dp[i][j] = dp[i][j] || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(p));
                }
            }
        }
        //dp[m][n]即表示字符串s1和字符串s2能够通过交织形成字符串s3
        return dp[m][n];
    }
}

一阶

class Solution {
    
    public boolean isInterleave(String s1, String s2, String s3) {
    
        //求出字符串 s1 s2 的长度为 m n
        int m = s1.length(),n = s2.length();
        //如果 m + n != 字符串s3的长度，那么s1和s2必不可能交织成s3
        if (m + n != s3.length()){
    
            return false;
        }
        //定义dp数组 dp[j] 表示字符串s2的前 j 个字符 与 字符串s1的前 i 个字符（假设s1的前i个字符一定能与s2配合交织形成s3） 能否通过交织得到字符串s3的子串[0,i+j)
        boolean[] dp = new boolean[n+1];
        //边界条件 dp[0] = true 根据我们dp的假设，s1和s2能否交织取决于s2，即s1会尽一切力量配合s2完成交织，所以当s2为空串时，我们的dp[0]应该等于 true
        dp[0] = true;
        //遍历字符串s1和s2 判断s1的前i个字符与s2的前j个字符能否交织能s3的子串[0,i+j)
        for (int i = 0; i <= m; i++) {
    
            //i 和 j 从 0 开始
            for (int j = 0; j <= n; j++) {
    
                //s3目标子串右边界
                int p = i+j-1;
                //一定选择s1
                if (i > 0){
    
                    //s1的第i个字符与s3的第i+j个字符相等，且交织方向为 s2 - s1 -> s3时，此时dp[j]的值取决于dp[j]本身
                    dp[j] = dp[j] && s1.charAt(i-1) == s3.charAt(p);
                }
                //一定选择s2
                if (j > 0){
    
                    //s2的第j个字符与s3的第i+j个字符相等，且交织方向为 s1 - s2 -> s3时，此时dp[j]的值取决于dp[j-1]
                    dp[j] = dp[j] || dp[j-1] && s2.charAt(j-1) == s3.charAt(p);
                }
            }
        }
        //dp[n]即表示字符串s1和字符串s2能否通过交织形成字符串s3
        return dp[n];
    }
}