# 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.**

**Show that***cchocohilaptes*is a shuffle of*chocolate*and*chips*, but*chocochilatspe*is not.**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()];

}