Edit distance variant — interleaving strings

We take a look at another variant of the edit distance problem — Interleaving strings.

8–2. Suppose you are given three strings of characters: X, Y, and Z, where |X|=n, |Y|=m, and |Z|=n+m. Z is said to be a shuffle of X and Y iff Z can be formed by interleaving the characters from X and Y in a way that maintains the left-to-right ordering of the characters from each string.

1. Show that cchocohilaptes is a shuffle of chocolate and chips, but chocochilatspe is not.
2. Give an efficient dynamic-programming algorithm that determines whether Z is a shuffle of X and Y. Hint: the values of the dynamic programming matrix you construct should be Boolean, not numeric.

In order to build up a recurrence relation, let’s try to figure out how to pick up characters to form the interleaved text.

If s1 = “a”, s2= “b” , s3 = “ba”

What are the possibilities ? s3 -> might be s1[0] + s2[0] or s3 might be s2[0] + s1[0]

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

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] && s2.charAt(j - 1) == s3.charAt(i+j-1);
                } else if(j == 0) {
                    dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i + j-1);
                } else {
                    dp[i][j] = dp[i][j-1] && s2.charAt(j - 1) == s3.charAt(i+j-1) ||
                        dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i + j-1);
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }