Interleaving String

NeetCode: Interleaving String · LeetCode: 97. Interleaving String · Difficulty: Medium

Given strings s1, s2 and s3, return true if s3 is formed by interleaving s1 and s2: both are split into substrings that are then merged alternately, and the characters of each original string keep their relative order.

Example

Text

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

Brute force: try both strings at every position

After using i characters of s1 and j of s2, the next character of s3 is at index i + j. It can come from s1[i] if they match, or from s2[j] if they match. Try both; if both match the recursion branches. Lengths must add up first, otherwise the answer is immediately false. Without memory the branching repeats the same (i, j) pairs.

Java

class Solution {
    private boolean go(String a, String b, String c, int i, int j) {
        if (i + j == c.length()) {
            return true;
        }
        char ch = c.charAt(i + j);
        return (i < a.length() && a.charAt(i) == ch && go(a, b, c, i + 1, j))
                || (j < b.length() && b.charAt(j) == ch && go(a, b, c, i, j + 1));
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        return go(s1, s2, s3, 0, 0);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbbaccc"));
        System.out.println(sol.isInterleave("", "", ""));
        System.out.println(sol.isInterleave("", "", "a"));
        System.out.println(sol.isInterleave("a", "", "a"));
    }
}

Output

true
false
true
false
true

Time: O(2^(m+n)) in the worst case. Space: O(m + n).

Better: 2D table

dp[i][j] is true when the first i characters of s1 and the first j of s2 can interleave into the first i + j characters of s3. It is true if the last character of s3's prefix came from s1 (dp[i-1][j] is true and s1[i-1] matches) or from s2 (dp[i][j-1] is true and s2[j-1] matches). There are only (m + 1) * (n + 1) states.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbbaccc"));
        System.out.println(sol.isInterleave("", "", ""));
        System.out.println(sol.isInterleave("", "", "a"));
        System.out.println(sol.isInterleave("a", "", "a"));
    }
}

Output

true
false
true
false
true

Time: O(m · n). Space: O(m · n).

Optimal: one rolling row

Row i only depends on row i - 1 (the value directly above) and its own left neighbour. Keep one array dp[j]; when processing cell j, dp[j] still holds the value from the previous row and dp[j - 1] is already the new value for this row.

Java

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int j = 1; j <= n; j++) {
            dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }
        for (int i = 1; i <= m; i++) {
            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char ch = s3.charAt(i + j - 1);
                boolean fromA = dp[j] && s1.charAt(i - 1) == ch;     // dp[j] is still the row above
                boolean fromB = dp[j - 1] && s2.charAt(j - 1) == ch; // dp[j - 1] is already this row
                dp[j] = fromA || fromB;
            }
        }
        return dp[n];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
        System.out.println(sol.isInterleave("aabcc", "dbbca", "aadbbbaccc"));
        System.out.println(sol.isInterleave("", "", ""));
        System.out.println(sol.isInterleave("", "", "a"));
        System.out.println(sol.isInterleave("a", "", "a"));
    }
}

Output

true
false
true
false
true

Time: O(m · n). Space: O(n).