[Algorithm] Leetcode #97 Interleaving String (DP-Hard) C++

Today, we’ll talk about Leetcode #97.

My initial approach was the topdown solution. We can add a few more conditions to the LCS problem. Let’s look at the code.

Topdown

Let i be an index for s1, j for s2 and n for s3. Then, compare the character at each position and track down all the way to the start. This approach is not an optimal solution. The time complexity is O(n²) 70m/s but recursive calls use a lot of call stacks. Instead, we can try the bottom up approach.

Here, dp[i][j] refers to whether the first i+j elements of s3 is the interleaving of the first i elements of s1 and the first j elements of s2.

Time Complexity: O(n²) 4m/s