(Dynamic Programming) Im having trouble in this code. Below is the original skel
ID: 3730595 • Letter: #
Question
(Dynamic Programming)
Im having trouble in this code. Below is the original skeleton code with the pseudocode
//package dp;
public class LCS {
public static int lcs_length (String X, String Y) {
/*
* fill in your code here
* Note: return the length of LCS, instead of c and b
*/
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(LCS.lcs_length("ABCBDAB", "BDCABA"));
System.out.println(LCS.lcs_length("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA", "GTCGTTCGGAATGCCGTTGCTCTGTAAA"));
}
}
***Screenshot of code above***
Instructions. You are provided one skeleton program named LCS.java. The source files are available on Canvas in a folder named HW6. Please modify the skeleton code to solve the following tasks plement the lcs lengthi fiinction as discussed in Lecture 11 Note: You should not return the double-array b and c as in the pse docode. Instead, return the length of the longest common subsequence Hint To get the i-th character in a string s, use s.charAt(i). For example, the code String s "XYZ" System.out.println(s.charAt(1)); prints out YExplanation / Answer
/* Dynamic Programming Java implementation of LCS problem */
public class LCS
{
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
public static int lcs_length( String str1, String str2 )
{
char[] X = str1.toCharArray();
char[] Y = str2.toCharArray();
int m = str1.length();
int n = str2.length();
int L[][] = new int[m+1][n+1];
/* Following steps build L[m+1][n+1] in bottom up fashion. Note
that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
return L[m][n];
}
/* Utility function to get max of 2 integers */
public static int max(int a, int b)
{
return (a > b)? a : b;
}
public static void main(String[] args)
{
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
System.out.println("Length of LCS is" + " " +
lcs_length(s1, s2) );
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.