[Algorithm] Leetcode #1143 Longest Common Substring (DP/Medium/C++)

Today, we’ll take a look at one of the most important DP categories, LCS. This question is quite self-intuitive in that the recurrence relation can be drawn in a simple manner.

Let’s look at an example.

s1 = “abcde”, s2 = “ace”. Then, the LCS would be “ace”.

First, let’s try to solve by topdown approach. The recurrence relation is self-explanatory. dp[i][j] = Length of longest common substring which can be formed by the first i elements of s1 and the first j elements of s2.

As we start from the end of s1 and s2, if s1[i]==s2[j], then we definitely obtains one common sub-character. If not, we compare the two situations: dropping the current character of s1 or s2. The final recurrence relation is,

Implementation — Top Down

Time Complexity: O(N²)

Implementation — Bottom Up

Time Complexity: O(n²)