【LeetCode】 97. Interleaving String 交错字符串（Hard）（JAVA）

【LeetCode】 97. Interleaving String 交错字符串（Hard）（JAVA）

题目地址: https://leetcode.com/problems/interleaving-string/

题目描述：

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

题目大意

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

解题方法

1、如果 i3 与 i1 或者 i2 其中一个相同，i1 或者 i2 进一位；如果两个都相同，两边都要判断
2、不断迭代，知道最后 s3 的结尾为止；用一个 Set 来保存，遍历过的 i1,i2,i3 （不保存竟然也可以过，但是耗时: 2611 ms）

class Solution {
    Set<String> set = new HashSet<>();
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        return iH(s1, s2, s3, 0, 0, 0);
    }

    public boolean iH(String s1, String s2, String s3, int i1, int i2, int i3) {
        if (i3 >= s3.length()) return true;
        if (set.contains(i1 + "-" + i2 + "-" + i3)) return false;
        if (i1 >= s1.length()) return s2.charAt(i2) == s3.charAt(i3) && iH(s1, s2, s3, i1, i2 + 1, i3 + 1);
        if (i2 >= s2.length()) return s1.charAt(i1) == s3.charAt(i3) && iH(s1, s2, s3, i1 + 1, i2, i3 + 1);
        
        if (s1.charAt(i1) == s3.charAt(i3) && iH(s1, s2, s3, i1 + 1, i2, i3 + 1)) return true;
        if (s2.charAt(i2) == s3.charAt(i3) && iH(s1, s2, s3, i1, i2 + 1, i3 + 1)) return true;
        set.add(i1 + "-" + i2 + "-" + i3);
        return false;
    }
}

执行用时 : 8 ms, 在所有 Java 提交中击败了 31.91% 的用户
内存消耗 : 38.3 MB, 在所有 Java 提交中击败了 14.29% 的用户

采用动态规划

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() != (s1.length() + s2.length())) return false;
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] && (s3.charAt(i + j - 1) == s2.charAt(j - 1));
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] && (s3.charAt(i + j - 1) == s1.charAt(i - 1));
                } else {
                    dp[i][j] = (dp[i - 1][j] && (s3.charAt(i + j - 1) == s1.charAt(i - 1))) || (dp[i][j - 1] && (s3.charAt(i + j - 1) == s2.charAt(j - 1)));
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
}

执行用时 : 4 ms, 在所有 Java 提交中击败了 74.91% 的用户
内存消耗 : 37.7 MB, 在所有 Java 提交中击败了 14.29% 的用户