Problem
statement : LCS DP (Longest Common Subsequence)
Given two strings. Find longest common subsequence/substring between the two strings:
Self understanding
Java Implementation
using Dynamic programming
package com.javadsalgo.Sorting;
public class LongestCommonSubsequence {
public static void main(String[] args) {
String
str1 = "ACBDEA";
String
str2 = "ABCDA";
System.out.println("LCS :"+ find(str1.toCharArray(),
str2.toCharArray()));
}
public static int find(char[] str1, char[] str2) {
int temp[][] = new int[str1.length + 1][str2.length + 1];
String[][]
solution = new String[str1.length + 1][str2.length +
1];
int max = 0;
for (int i = 1; i < temp.length;
i++) {
for (int j = 1; j < temp[i].length;
j++) {
if (str1[i - 1] == str2[j - 1]) {
temp[i][j]
= temp[i - 1][j - 1] + 1;
solution[i][j] = "diagonal";
}
else {
temp[i][j]
= Math.max(temp[i][j - 1], temp[i - 1][j]);
if (temp[i][j] == temp[i - 1][j]) {
solution[i][j] = "top";
}
else {
solution[i][j] = "left";
}
}
if (temp[i][j] > max) {
max
= temp[i][j];
}
}
}
String
sol= solution[str1.length][str2.length];
String
answer="";
int x=str1.length,y=str2.length;
while(sol!=null){
if(solution[x][y].equals("diagonal"))
{
answer+=str1[x-1];
x--;y--;
}
else if(solution[x][y].equals("top"))
x--;
else if(solution[x][y].equals("left"))
y--;
sol=solution[x][y];
}
StringBuffer
rev= new StringBuffer(answer);
System.out.println("LCS is "+rev.reverse());
return max;
}
}
References
No comments:
Post a Comment