LeetCode刷题系列 -- 97. 交错字符串

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ... 注意：a + b 意味着字符串 a 和 b 连接。

思路：

若是 s1.length + s2.length != s3.length 时，显然此刻大罗神仙也办不到 s1与 s2交错得到 s3，直接返回false 此题用动态规划 1. 定义二维数组 dp[s1.length+1][s2.length+1] , dp[i][j] 代表 s1[0,...,i-1] 与 s2[0,...,j-1]是否可以交错生成 s3[0,...,i+j-1] 2. 初始化base，dp[0][0] 代表两个空字符串是否可以交错成另一个空字符串，这个我们默认是可以的，故 dp[0][0] = true 2. 若是 s1.length + s2.length == s3.length 时， 2.1）若是 s1[i-1] != s3[i+j-1] && s2[j-1] != s3[i+j-1] ，则 dp[i][j] = false 2.2) 若是 s1[i-1] == s3[i+j-1] , 此时说明，若是s1[0,...,i-2] 与 s2[0,...,j-1] 可以交错生成 s3[0,...,i+j-1],则表示 s1[0,...,i-1] 与 s2[0,...,j-1] 可以交错生成 s3[0,...,i+j-1], 即dp[i][j] = dp[i-1][j] 若是 s2[j-1] == s3[i+j-1] , 此时说明，若是s1[0,...,i-1] 与 s2[0,...,j-2] 可以交错生成 s3[0,...,i+j-1],则表示 s1[0,...,i-1] 与 s2[0,...,j-1] 可以交错生成 s3[0,...,i+j-1], 即dp[i][j] = dp[i][j-1]

java代码：

class Solution {
       public boolean isInterleave(String s1, String s2, String s3) {
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];

        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        // 1. 初始化base
        dp[0][0] = true;

        for(int i=1;i<s1.length()+1;i++) {
            if(s1.charAt(i-1) == s3.charAt(i-1) && dp[i-1][0]) {
                dp[i][0] = true;
            }
        }
        for(int j=1;j<s2.length()+1;j++) {
            if(s2.charAt(j-1) == s3.charAt(j-1) && dp[0][j-1]) {
                dp[0][j] = true;
            }
        }

        // 2. 更新dp
        for (int i = 1; i < s1.length() + 1; i++) {
            for (int j = 1; j < s2.length() + 1; j++) {
                   if (s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
                    dp[i][j] = dp[i - 1][j];
                } 
                if (s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
                    dp[i][j] = dp[i][j - 1]||dp[i][j];
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
}