Leetcode 1143. Longest Common Subsequence
Problem
The given problem is to find the longest common subsequence between two strings text1 and text2. A subsequence is a string that is derived from the original string by deleting some (may be none) characters without changing the order of the remaining characters. For example "ace" is a subsequence of "abcde". A common subsequence of two strings is a subsequence which is common in both strings.
If there are no common subsequences, we return 0.
For example:
Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.
In this problem, the length of both strings will be between 1 and 1000 and will only consists of lowercase English characters.
Approach
The problem can be solved using the concept of dynamic programming. The basic idea is to generate a 2D array dp
where dp[i][j]
represents the length of the longest common subsequence of text1[0..i)
and text2[0..j)
.
We begin by iterating over each character of the two strings. If the characters at the current indices of the two strings are equal, we increment the length of the longest common subsequence found till now which will be stored at dp[i][j]
i.e. one element diagonally above the current element. On the other hand, if the characters are not equal, we take the maximum of dp[i][j + 1]
and dp[i + 1][j]
which represent the length of the longest common subsequence found by excluding the current character from either of the two strings.
Finally, dp[m][n]
will give us the length of the longest common subsequence of the two input strings where m
and n
are the lengths of the two input strings.
Java Solution
1 2java 3class Solution { 4 public int longestCommonSubsequence(String text1, String text2) { 5 int m = text1.length(); 6 int n = text2.length(); 7 int[][] dp = new int[m + 1][n + 1]; 8 9 for (int i = 0; i < m; i++) { 10 for (int j = 0; j < n; j++) { 11 if (text1.charAt(i) == text2.charAt(j)) { 12 dp[i + 1][j + 1] = 1 + dp[i][j]; 13 } else { 14 dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]); 15 } 16 } 17 } 18 19 return dp[m][n]; 20 } 21}
Python Solution
1 2python 3class Solution: 4 def longestCommonSubsequence(self, text1: str, text2: str) -> int: 5 m, n = len(text1), len(text2) 6 dp = [[0]*(n+1) for _ in range(m+1)] 7 8 for i in range(m): 9 for j in range(n): 10 if text1[i] == text2[j]: 11 dp[i+1][j+1] = dp[i][j] + 1 12 else: 13 dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]) 14 15 return dp[-1][-1]
Javascript Solution
1 2javascript 3var longestCommonSubsequence = function(text1, text2) { 4 const m = text1.length, n = text2.length; 5 const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0)); 6 7 for (let i = 0; i < m; i++) { 8 for (let j = 0; j < n; j++) { 9 if (text1[i] === text2[j]) { 10 dp[i + 1][j + 1] = 1 + dp[i][j]; 11 } else { 12 dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]); 13 } 14 } 15 } 16 return dp[m][n]; 17};
C++ Solution
1 2cpp 3class Solution { 4public: 5 int longestCommonSubsequence(string text1, string text2) { 6 int m = text1.size(), n = text2.size(); 7 vector<vector<int>> dp(m+1,vector<int> (n+1,0)); 8 for(int i = 0; i < m; i++) { 9 for(int j = 0; j < n; j++) { 10 if(text1[i] == text2[j]) 11 dp[i+1][j+1] = dp[i][j] + 1; 12 else 13 dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); 14 } 15 } 16 return dp[m][n]; 17 } 18};
C# Solution
1 2csharp 3public class Solution { 4 public int LongestCommonSubsequence(string text1, string text2) { 5 int m = text1.Length, n = text2.Length; 6 int[,] dp = new int[m+1, n+1]; 7 8 for (int i = 0; i < m; i++) { 9 for (int j = 0; j < n; j++) { 10 if (text1[i] == text2[j]) { 11 dp[i+1, j+1] = 1 + dp[i, j]; 12 } else { 13 dp[i+1, j+1] = Math.Max(dp[i, j+1], dp[i+1, j]); 14 } 15 } 16 } 17 return dp[m, n]; 18 } 19}
Ruby Solution
1 2ruby 3def longest_common_subsequence(text1, text2) 4 m, n = text1.length, text2.length 5 dp = Array.new(m+1) {Array.new(n+1, 0)} 6 7 for i in 0...m 8 for j in 0...n 9 if text1[i] == text2[j] 10 dp[i+1][j+1] = dp[i][j] + 1 11 else 12 dp[i+1][j+1] = [dp[i][j+1], dp[i+1][j]].max 13 end 14 end 15 end 16 return dp[-1][-1] 17end
PHP Solution
1
2php
3function longestCommonSubsequence($text1, $text2) {
4 $m = strlen($text1);
5 $n = strlen($text2);
6 $dp = array_fill(0, $m+1, array_fill(0, $n+1, 0));
7
8 for ($i = 0; $i < $m; $i++) {
9 for ($j = 0; $j < $n; $j++) {
10 if ($text1[$i] == $text2[$j]) {
11 $dp[$i+1][$j+1] = 1 + $dp[$i][$j];
12 } else {
13 $dp[$i+1][$j+1] = max($dp[$i][$j+1], $dp[$i+1][$j]);
14 }
15 }
16 }
17 return $dp[$m][$n];
18}
In conclusion, the longest common subsequence problem is a classic dynamic programming problem that can be solved with a straightforward tabulation approach. We benefit from the overlapping subproblems and optimal substructure properties of the problem and build a table to store our subproblem solutions. By iterating over the characters of both strings, the text1 and text2, we can fill up our table and ultimately find the length of their longest common subsequence in the last cell of our table. The concept is essentially the same across all programmed languages. The syntax may vary between languages, but the underlying principles remain consistent. Furthermore, the concept of dynamic programming remains one of the most fundamental aspects of computer science, and it is utilized in a wide range of problems beyond just longest common subsequence.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.