Dynamic programming problems solution to interleaving strings

Question

I was trying to solve this problem, and I gave up, and found the solution below, although I do not understand how the solution works, or why it works. Any in-depth solution would be deeply appreciated.

Question:

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

For example, Given:

s1 = "aabcc"
s2 = "dbbca"

• When s3 = "aadbbcbcac", return true.
• When s3 = "aadbbbaccc", return false.

Solution:

  public static boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() == 0 && s1.length() == 0 && s2.length() == 0)
            return true;

        else if (s3.length() != s1.length() + s2.length())
            return false;
        boolean isInter[][] = new boolean[s1.length()+1][s2.length()+1];
        isInter[0][0] = true;
        for ( int i = 1; i <= s1.length(); ++i){
            if (s1.charAt(i-1) == s3.charAt(i-1))
                isInter[i][0] = true;
            else
                break;
        }
        for ( int i = 1; i <= s2.length(); ++i){
            if (s2.charAt(i-1) == s3.charAt(i-1))
                isInter[0][i] = true;
            else
                break;
        }
        // DP
        for ( int i = 1; i <= s1.length(); ++i){
            for ( int j = 1; j <= s2.length(); ++j){
                if (s3.charAt(i+j-1) == s1.charAt(i-1))
                    isInter[i][j] = isInter[i-1][j] || isInter[i][j];
                if (s3.charAt(i+j-1) == s2.charAt(j-1))
                    isInter[i][j] = isInter[i][j-1] || isInter[i][j];
            }
        }
        return isInter[s1.length()][s2.length()];
    }

Answer 1

I'm using Python slice syntax here because it is nice. S[:-1] means the string S with its last character removed and S[:n] means the prefix of S that has length n.

The key idea is that if C is an interleaving of A and B, then C[:-1] is either an interleaving of A and B[:-1] or of A[:-1] and B. On the other hand, if C is an interleaving of A and B, then C + 'X' is an interleaving of A + 'X' and B and it is also an interleaving of A and B + 'X'.

These are the substructure properties we need to apply dynamic programming.

We define f(i, j) = true, if s1[:i] and s2[:j] can be interleaved to form s3[:(i+j)] and f(i,j) = false otherwise. By the observation above we have

f(0,0) = true
f(i,0) = f(i-1, 0) if s3[i-1] == s1[i-1]
f(0,j) = f(0, j-1) if s3[j-1] == s2[j-1]
f(i,j) = true if s3[i+j-1] = s1[i-1] and f(i-1, j)
f(i,j) = true if s3[i+j-1] = s2[j-1] and f(i, j-1)

In all the other cases we have f(i,j) = false. The Java code just implements this recurrence using dynamic programming. That said, I would implement it in a bit more concise way:

for (int i = 0; i <= s1.length(); ++i)
    for (int j = 0; j <= s2.length(); ++j)
        isInter[i][j] = (i == 0 && j == 0)
           || (i > 0 && s1.charAt(i-1) == s3.charAt(i+j-1) && isInter[i-1][j])
           || (j > 0 && s2.charAt(j-1) == s3.charAt(i+j-1) && isInter[i][j-1]);

Answer 2

The first few lines just deal with simple cases that can be resolved based only on the input string lengths. These tests simplify the remaining code by allowing it to assume that the lengths match.

The guts of the algorithm calculate an array isInter, where isInter[i][j] is true after iteration (i,j) if, and only if, the first i+j characters of s3 can be formed by interleaving the first i characters of s1 with the first j characters of s2.

isInter[i][0] is true if, and only if, the first i characters of s3 match the first i characters of s1. Similarly, isInter[0][i] is true if, and only if, the first i characters of s3 match the first i characters of s2.

The final loop builds up the remaining elements of isInter using already calculated elements and matches between the next character of s3 and either the next character of s1 or the next character of s2.

After isInter has been completely calculated, isInter[s1.length()][s2.length()] is true if, and only if, the whole of s3 can be formed by interleaving the whole of s1 with the whole of s2.