Leetcode 97: Interleaving String

I used recursion with DP memoization. A simple recursive solution will be O(2n) because there can potentially be a lot of repeating subtrees in the call graph. Memoization cuts out these duplicated paths. The idea is to recursively try all possibilities until we reach a complete match. At each step we either move forward one position in s1 and s3 of the current characters are the same or we move forward one position in s2 and s3 if those characters are the same.

In solution B below I used iterative DP. I used a 2D DP table with booleans to signify if reaching those positions in s1 and s2 is possible. Build the table by using the next character in s1 by moving down or using the next character in s2 by moving right. So we can figure out a dp result by building on previous results up and left. Our final result at the bottom right of the table is wether it is possible to get to the end of both strings s1 and s2.

Here’s the iterative DP solution:
And here’s the recursive with memoization solution:

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.