Poison

97. Interleaving String

发表于
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        // 定义 dp[i][j] 为 s1 中前 i 个字符与 s2 中前 j 个字符是否可以交错组成 s3 中的前 i + j 个字符
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true; // 空字符串与空字符串可以组成空字符串

        for (int i = 1; dp[i - 1][0] && i <= s1.length(); i++) {
            // s2 为空字符串时
            dp[i][0] = s1.charAt(i - 1) == s3.charAt(i - 1);
        }

        for (int j = 1; dp[0][j - 1] && j <= s2.length(); j++) {
            // s1 为空字符串时
            dp[0][j] = s2.charAt(j - 1) == s3.charAt(j - 1);
        }

        // i, j 代表前 i, j 个字符串
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); 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];
                }
            }
        }

        return dp[s1.length()][s2.length()];
    }
}
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        // 定义 dp[i][j] 为 s1 中前 i 个字符与 s2 中前 j 个字符是否可以交错组成 s3 中的前 i + j 个字符
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true; // 空字符串与空字符串可以组成空字符串

        // i, j 代表前 i, j 个字符串
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
                    dp[i][j] |= dp[i - 1][j];
                }
                if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
                    dp[i][j] |= dp[i][j - 1];
                }
            }
        }

        return dp[s1.length()][s2.length()];
    }
}
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        // 定义 dp[j] 为 s2 中前 j 个字符是否可以交错组成 s3 中的前 j 个字符
        boolean[] dp = new boolean[s2.length() + 1];
        dp[0] = true; // 空字符串与空字符串可以组成空字符串

        // i, j 代表前 i, j 个字符串
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i > 0 && s1.charAt(i - 1) != s3.charAt(i + j - 1)) {
                    dp[j] = false;
                }
                if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
                    dp[j] |= dp[j - 1];
                }
            }
        }

        return dp[s2.length()];
    }
}
Reference

97. Interleaving String