Interleaving String

Given strings s1, s2, and s3, return true if s3 is an interleaving of s1 and s2: it contains all the characters of both, and the characters of each string appear in their original order.

LeetCode: 97. Interleaving String

Example

Text

s1 = "xxyzz", s2 = "wyyzx", s3 = "xxwyyzyzxz"  ->  true
     "xx" (s1) + "wyyz" (s2) + "yz" (s1) + "x" (s2) + "z" (s1)

s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"  ->  true
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"  ->  false

Brute force: branch on each character

After using i characters of s1 and j of s2, the next character of s3 is s3[i + j]. It must come from s1[i] or s2[j]. When both match, try both.

Java

public class Main {
    static boolean interleaves(String s1, String s2, String s3, int i, int j) {
        if (i + j == s3.length()) return true;
        char c = s3.charAt(i + j);
        return (i < s1.length() && s1.charAt(i) == c && interleaves(s1, s2, s3, i + 1, j))
            || (j < s2.length() && s2.charAt(j) == c && interleaves(s1, s2, s3, i, j + 1));
    }

    static boolean isInterleave(String s1, String s2, String s3) {
        return s1.length() + s2.length() == s3.length() && interleaves(s1, s2, s3, 0, 0);
    }

    public static void main(String[] args) {
        System.out.println(isInterleave("xxyzz", "wyyzx", "xxwyyzyzxz"));
        System.out.println(isInterleave("aabcc", "dbbca", "aadbbcbcac") + " " + isInterleave("aabcc", "dbbca", "aadbbbaccc"));
    }
}

Output

true
true false

Time: O(2^(m+n)) in the worst case (for example, strings made of the same letter). Space: O(m + n) for the recursion.

Optimal: a table over prefixes

The recursion only depends on (i, j), and there are (m + 1)(n + 1) such pairs. Let ok[i][j] be true if the first i characters of s1 and the first j characters of s2 interleave to form the first i + j characters of s3. The last of those characters came from s1 or from s2:

Text

ok[i][j] = (ok[i-1][j] && s1[i-1] == s3[i+j-1])
        || (ok[i][j-1] && s2[j-1] == s3[i+j-1])

Each row only needs the row above it, so one array indexed by j, updated in place, is enough.

Java

public class Main {
    static boolean isInterleave(String a, String b, String c) {
        if (a.length() + b.length() != c.length()) return false;
        boolean[] ok = new boolean[b.length() + 1];
        for (int i = 0; i <= a.length(); i++) {
            for (int j = 0; j <= b.length(); j++) {
                if (i == 0 && j == 0) {
                    ok[j] = true;
                } else {
                    boolean fromA = i > 0 && ok[j] && a.charAt(i - 1) == c.charAt(i + j - 1); // ok[j] still holds row i - 1
                    boolean fromB = j > 0 && ok[j - 1] && b.charAt(j - 1) == c.charAt(i + j - 1); // ok[j - 1] is already row i
                    ok[j] = fromA || fromB;
                }
            }
        }
        return ok[b.length()];
    }

    public static void main(String[] args) {
        System.out.println(isInterleave("xxyzz", "wyyzx", "xxwyyzyzxz"));
        System.out.println(isInterleave("aabcc", "dbbca", "aadbbcbcac") + " " + isInterleave("aabcc", "dbbca", "aadbbbaccc"));
        System.out.println(isInterleave("", "", "") + " " + isInterleave("a", "", "b"));
    }
}

Output

true
true false
true false

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

Edge cases

Lengths don't add up: false immediately.
Empty strings: "" + "" interleave to ""; with one string empty, s3 must equal the other.
Characters common to both strings: exactly the case where a greedy choice fails and the DP is needed.