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:
https://gist.github.com/adamkorg/a90aaf22791215c44bfffae9f3f4ca6e
And here’s the recursive with memoization solution: