Longest Common Subsequence (#1143 Leetcode)

 Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings. 

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

1. Comparing character by character in each texts, the first character matches in both texts. 

2. So, we will strike out the first character in both texts.

3. Comparing the character b in text 1, and c in text 2 will not match. So we will eventually have two decisions. 

    a) Skipping/Ignoring character b from text1

         Compare 'cde' in text 1 with 'ce' in text 2

    b) Skipping/Ignoring character c from text2

         Compare 'bcde' in text 1 with 'e' in text 2

4. It keeps going in this way. 

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

 

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Optimal Solution: 

A common subsequence between two sequences define a non-crossing matching between the two sequences. 

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        short m = text1.size(), n = text2.size();
        short dp[m+1][n+1];
        for (int i = 0; i <= m; i++) {
           dp[i][0] = 0;
        }
        for (int i = 0; i <= n; i++) {
           dp[0][i] = 0;
        }
        for (int i = 1; i <= m; i++) {
           for (int j = 1; j <= n; j++) {
              dp[i][j] = (text1[i-1] == text2[j-1]) ? (dp[i-1][j-1] + 1) : max(dp[i-1][j], dp[i][j-1]);
              
           }
        }
        return dp[m][n];
    }
};

Dynamic Programming always come with recursive formulation. 

Dry-Run of the algorithm