Example: String Verify interleaving - rFronteddu/general_wiki GitHub Wiki

You are given 3 strings, s1, s2, s3, and have to verify if s3 is made by interleaving s1 and s2.

ex.

• s1: a, x, y
• s2: a, a, b
• s3: a, a, x, a, b, y

---	0	a	a	b
0
a
x
y

• d[i,j] will be true if the first i characters of s1 and the first j characters of s2 can form the first i+j characters of s3.

• We populate d[0,0] is true because two empty strings can form an empty string

---	0	a	a	b
0	T
a
x
y

• first row we only consider characters from s2, if s2[j-1] == s3[j-1] then d[0,j] = d[0,j-1]
• for the first col we only consider characters from s1, if s1[i-1] == s3[i-1] then d[i,0] = d[i-1,0]

---	0	a	a	b
0	T	T	T	F
a	T
x	F
y	F

• for each d[i,j] we check if one of two conditions holds
  • if i-th character of s1 matches i+j th character of s3, then d[i,j]=d[i-1,j]
  • if j-th character of s2 matches i+j-th character of s3, then d[i,j]=d[i,j-1]
  • => d[i,j] = s1[i] == s3[i+j] && d[i-1,j] || s2[j] == s3[i+j] && d[i,j-1]

---	0	a	a	b
0	T	T	T	F
a	T	T	F	F
x	F	T	T	T
y	F	F	F	T

isInterleaved(s1, s2, s3)
    n = s1.len
    m = s2.len
    // If the lengths don't add up, s3 can't be an interleaving of s1 and s2
    if n + m != s3.len
        return false

    let d[0..n, 0..m] be a 2d array of Boolean values initialized to false 
    d[0,0] = true

    // initialize first col and row using only s1 and s2 respectively
    for i = 1 to n
        if s1[i-1] == s3[i-1]
            d[i,0] = d[i-1,0]
  
    for j = 1 to m
        if s2[j-1] == s3[j-1]
            d[0,j] = d[0,j-1]

    for i = 1 to n
        for j = 1 to m
            d[i,j] = (s1[i-1] == s3[i+j-1] && d[i-1,j]) || (s2[j-1] == s3[i+j-1] && d[i,j-1])         

   return d[n,m]