Given two strings s1 and s2 of length m and n respectively and a bigger string S of length m+n , design an algorithm to find whether S is formed by interleaving of s1 and s2. What’s the complexity of the algorithm.
I think a dynamic alg could solve it.
let f(i,j) represent a.substring(i,a.len), b.substring(j,b.len) could match s.substring(i+j,s.len)
f(i,j)|= f(i+1,j) if a[i]==s[i+j]
f(i,j)|= f(i,j+1) if b[j]==s[i+j]
so the complexity is O(m*n)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment