Given two strings

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 <= 1000 1 <= text2.length <= 1000 - The input strings consist of lowercase English characters only.

#### Solution

Its a standard DP problem to find LCS sequence, Maintain DP matrix for previous states, Use previous states to calculate the current state.

###### Code

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public class LongestCommonSubSeq { public int longestCommonSubsequence(String text1, String text2) { int n = text1.length(), m = text2.length(); int[][] dp = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[n][m]; } public static void main(String[] args) { System.out.println(new LongestCommonSubSeq().longestCommonSubsequence("abcde", "ace")); } } |

#### Output

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.