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:
Example 2:
Example 3:
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.