1143. Longest Common Subsequence
https://leetcode.com/problems/longest-common-subsequence/
Given two strings text1 and text2, return the length of their longest common subsequence.
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. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.
Example 1:
Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.
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 <= 10001 <= text2.length <= 1000- The input strings consist of lowercase English characters only.
----
Intuition
Nested loop on both strings
if chars match
len of LCS = 1 + len of LCS of previous positions of both
else
len of LCS = max(len of LCS ignoring char from S1, len of LCS ignoring char from S2)
dp - init to size of S1, S2
Loop from 1 to = S.length()
if (char(i - 1) == char(j - 1)
dp[i][j] = 1 + dp[i - 1][j - 1]
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[S1.len()][S2.len()]
----
Time - O(m * n)
Space - O(m * n)
Can optimize on space with 2 rows, and columns of smaller string
Time - O(m * n)
Space - O(min(m, n))
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int longestCommonSubsequence(String text1, String text2) { | |
| // reduce space - min # of columns | |
| if (text2.length() > text1.length()) { | |
| return longestCommonSubsequence(text2, text1); | |
| } | |
| int[][] dp = new int[2][text2.length() + 1]; | |
| for (int i = 1; i <= text1.length(); i++) { | |
| for (int j = 1; j <= text2.length(); j++) { | |
| if (text1.charAt(i - 1) == text2.charAt(j - 1)) { | |
| dp[1][j] = 1 + dp[0][j - 1]; | |
| } else { | |
| dp[1][j] = Math.max(dp[0][j], dp[1][j - 1]); | |
| } | |
| } | |
| dp[0] = dp[1].clone(); | |
| } | |
| return dp[1][text2.length()]; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int longestCommonSubsequence(String text1, String text2) { | |
| int[][] dp = 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.charAt(i - 1) == text2.charAt(j - 1)) { | |
| dp[i][j] = 1 + dp[i - 1][j - 1]; | |
| } else { | |
| dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); | |
| } | |
| } | |
| } | |
| return dp[text1.length()][text2.length()]; | |
| } | |
| } |
