[LeetCode] Longest Common Subsequence

Problem: 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:

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

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

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

Approach: Obviously we are going to use DP here. We are going to maintain a 2D table where table[i][j] will tell the longest common subsequence of substrings text1[0...i] and text2[0...j]. Here is how we can fill the table:

• IF text1[i] == text2[j] then table[i][j] = table[i - 1][j - 1] + 1
• ELSE table[i][j] = MAX(table[i - 1][j], table[i][j - 1]

In the end we will return table[len1-1][len2-1] where len1 and len2 are the length of text1 and text2 respectively.

Implementation in C#:

    public int LongestCommonSubsequence(string text1, string text2) 

    {

        int[,] table = new int[text1.Length + 1, text2.Length + 1];

        for (int i = 1; i <= text1.Length; ++i)

        {

            for (int j = 1; j <= text2.Length; ++j)

            {

                if (text1[i - 1] == text2[j - 1])

                {

                    table[i, j] = table[i - 1, j - 1] + 1;

                }

                else

                {

                    table[i, j] = Math.Max(table[i - 1, j], table[i, j - 1]);

                }

            }

        }

        return table[text1.Length, text2.Length];

    }

Complexity: O(m * n) where m is the length of text1 and n is the length of text2.