Skip to content

Instantly share code, notes, and snippets.

@warlock2k
Last active June 1, 2020 06:05
Show Gist options
  • Save warlock2k/e45de4a394e9b8a384c2d0c499c6fceb to your computer and use it in GitHub Desktop.
Save warlock2k/e45de4a394e9b8a384c2d0c499c6fceb to your computer and use it in GitHub Desktop.
import java.util.*;
public class LCS2
{
/*
* As usual for DP, three Steps are involved:
* 1. Break down the main problem into sub problems.
* 2. Initialize cache to hold solutions to sub problems.
* 3. Build solution to main problem from sub problem.
* Refer to this https://youtu.be/ASoaQq66foQ (Back To Back SWE)
*/
private static int lcs2(int[] a, int[] b)
{
// a & b represent two strings.
// longestCommonSubSequence is a axb matrix of two strings.
int [][] longestCommonSubSequence = new int [a.length + 1][b.length + 1];
// Initialize all all elements in first column to zero.
for (int i = 0; i <= a.length; i++)
{
longestCommonSubSequence[i][0] = 0;
}
// Initialize all all elements in first row to zero.
for (int j = 0; j <= b.length; j++)
{
longestCommonSubSequence[0][j] = 0;
}
// Iterate through each character of a
for (int i = 1; i <= a.length; i++)
{
// Iterate through each character of b for each element of a.
for (int j = 1; j <= b.length; j++)
{
// The subproblem is to look at the last character of each string.
// Two possibilites exist, they can be equal, they need not be equal.
if (a[i-1] == b[j-1])
{
// as they are equal, simply do 1 + longestCommonSubSequence(subProblem).
longestCommonSubSequence[i][j] = longestCommonSubSequence[i-1][j-1] + 1;
}
else
{
// If they are not equal, check if removing of the last character from either of two strings yields longest commond subsequence.
longestCommonSubSequence[i][j] = Math.max(longestCommonSubSequence[i-1][j], longestCommonSubSequence[i][j-1]);
}
}
}
return longestCommonSubSequence[a.length][b.length];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
int m = scanner.nextInt();
int[] b = new int[m];
for (int i = 0; i < m; i++) {
b[i] = scanner.nextInt();
}
System.out.println(lcs2(a, b));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment