DP-Longest Common Subsequence

Question 1

1143. 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.

TC –
SC –

Answer 1

Pseudo code:
1. Declare 2D matrix where row size will be text1 length plus 1 and col size will be text1 length plus 1.
2. Row represents text1 and col represents text2.
3. Loop throw row with 1st index, col with 1st index.
a. If first char of both the string matches then increase count with 1 and move on next search with text1 without first char and text2 without first char.
b. Else max of below.
longestCommonSubsequence(text1, text2 without last first) OR
longestCommonSubsequence (text2, text1 without last first)
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
for (int i = 0; i < text1.length(); ++i)
for (int j = 0; j < text2.length(); ++j)
if (text1.charAt(i) == text2.charAt(j))
dp[i + 1][j + 1] = 1 + dp[i][j];
else
dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
return dp[text1.length()][text2.length()];
}