Longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences
Given two string and find the common sentence in the both
source Code
package com.dsacode.Algorithm.dynamic; import java.util.Arrays; public class LongestCommon { public static String x = "Hello"; public static String y = "Helloworld"; public static void main(String [] args) { int[][] memo = new int[x.length()+1][y.length()+1]; for (int i = 0; i < memo.length; i++) Arrays.fill(memo[i], -1); System.out.println("Longest Common String of '"+ x + "' and '"+ y + "' using dynamic programming = "+lcsdyn()); } public static int lcsdyn() { int i,j; int lenx = x.length(); int leny = y.length(); int[][] table = new int[lenx+1][leny+1]; for (i = 0; i <= lenx; i++) table[i][0] = 0; for (i = 0; i <= leny; i++) table[0][i] = 0; for (i = 1; i <= lenx; i++) { for (j = 1; j <= leny; j++) { if (x.charAt(i-1) == y.charAt(j-1)) table[i][j] = 1+table[i-1][j-1]; else table[i][j] = Math.max(table[i][j-1], table[i-1][j]); } } return table[lenx][leny]; } }
Output
Longest Common String of 'Hello' and 'Helloworld' using dynamic programming = 5
Algorithm Explanation
![]() | Pass string arguments to the utility function. |
![]() | Take the length of two strings and divide the problems into subproblems. |
![]() | Compute the subproblem solution and memorize to improve the time complexity. |
![]() | Return solution to the main function and print the solution. |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
– | O(mn)) | – |