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()];
}

I’m a software engineer with a strong interest in algorithms. I love solving puzzles and love the aha moment of arriving at a solution after hours of struggle.