DP #31. String Interleaving - mbhushan/dynpro GitHub Wiki

(31). String Interleaving.

Given three strings A, B and C. Write a function that checks whether C is an 
interleaving of A and B. C is said to be interleaving A and B, if it contains 
all characters of A and B and order of all characters in individual strings is 
preserved.
A = "XXY"
B = "XXZ"
C = "XXXXZY"

output: True.
Formula:

if (B[i] == C[i+j]) {
     T[i][j] = T[i][j-1]
} else if (A[j] == C[i+j]) {
    T[i][j] = T[i-1][j]
} else {
    T[i][j] = false;
}
0 X X Y
0 T T T F
X T T T F
X T T T F
Z F F T T(ans)

String Interleaving

  • Time Complexity: O(n * m)
  • Space Complexity: O(n * m)