97. Interleaving String

二刷 07/2022

Version #2 Optimized DP

Time O(MN)

Space O(N)

Runtime: 6 ms, faster than 52.14% of Java online submissions for Interleaving String.

Memory Usage: 41.8 MB, less than 81.71% of Java online submissions for Interleaving String.

class Solution {

    public boolean isInterleave(String s1, String s2, String s3) {

        if (s1.length() + s2.length() != s3.length()) {

            return false;

        }

        // dp[i][j] - if s1.substring(i) and s2.substring(j) can form s3.substring(i + j)

        boolean[] dp = new boolean[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[0] = true;

                    continue;

                }

                char c = s3.charAt(i + j - 1);

                if (i == 0) {

                    dp[j] = c == s2.charAt(j - 1) && dp[j - 1];

                    continue;

                }

                if (j == 0) {

                    dp[0] = c == s1.charAt(i - 1) && dp[0];

                    continue;

                }

                dp[j] = (c == s1.charAt(i - 1) && dp[j]) || (c == s2.charAt(j - 1) && dp[j - 1]);

            }

        }

        return dp[s2.length()];

    }

}

一刷

Version # 2 Optimized DP
Time O(mn) Space O(n)
73.41 %
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
// dp[i][j] -> s1[0, p1), s2[0, p2) can form s3[0, p1 + p2)
if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()) {
return false;
}
int p1 = 0;
int p2 = 0;
boolean[] dp = new boolean[s2.length() + 1];
dp[0] = true;
// p1 = 0;
for (p2 = 1; p2 <= s2.length(); p2++) {
dp[p2] = dp[p2 - 1] && s2.charAt(p2 - 1) == s3.charAt(p2 - 1);
}
for (p1 = 1; p1 <= s1.length(); p1++) {
dp[0] = dp[0] && s1.charAt(p1 - 1) == s3.charAt(p1 - 1);
for (p2 = 1; p2 <= s2.length(); p2++) {
dp[p2] = dp[p2 - 1] && s2.charAt(p2 - 1) == s3.charAt(p1 + p2 - 1)
                    || dp[p2] && s1.charAt(p1 - 1) == s3.charAt(p1 + p2 - 1);
}
}
return dp[s2.length()];
}
}


Version #1 Naive DP
Time O(mn)
Space O(mn)

54.98 %

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
// dp[i][j] -> s1[0, p1), s2[0, p2) can form s3[0, p1 + p2)
        if (s1 == null && s2 == null) {
            return s3 == null;
        }
        if (s1 == null || s1.length() == 0) {
            return s2.equals(s3);
        }
        if (s2 == null || s2.length() == 0) {
            return s1.equals(s3);
        }
if (s1.length() + s2.length() != s3.length()) {
return false;
}
int p1 = 0;
int p2 = 0;
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
for (p1 = 0; p1 <= s1.length(); p1++) {
            dp[p1][0] = p1 == 0 ? true : dp[p1 - 1][0] && s1.charAt(p1 - 1) == s3.charAt(p1 - 1);
for (p2 = 1; p2 <= s2.length(); p2++) {
// start with p2
if (p1 + p2 - 1 >= s3.length()) {
return false;
}
if (p1 == 0) {
dp[p1][p2] = dp[p1][p2 - 1] && s2.charAt(p2 - 1) == s3.charAt(p1 + p2 - 1);
} else {
dp[p1][p2] = (dp[p1][p2 - 1] && s2.charAt(p2 - 1) == s3.charAt(p1 + p2 - 1))
|| (dp[p1 - 1][p2] && s1.charAt(p1 - 1) == s3.charAt(p1 + p2 - 1));
}
}
}
return dp[s1.length()][s2.length()];
}
}