Created
March 28, 2018 17:00
-
-
Save avijitmondal/c1d53d5db6681c27538b9581830c7df8 to your computer and use it in GitHub Desktop.
Given with the two strings we have to find the longest common sub-sequence present in both of them
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class LCS { | |
| public static void main(String[] args) { | |
| // TODO Auto-generated method stub | |
| String str1 = "AGGTAB"; | |
| String str2 = "GXTXAYB"; | |
| LCS obj = new LCS(); | |
| System.out.println(obj.lcs(str1, str2, str1.length(), str2.length())); | |
| System.out.println(obj.lcs2(str1, str2)); | |
| } | |
| //Recursive function | |
| public int lcs(String str1, String str2, int m, int n) { | |
| if (m == 0 || n == 0) | |
| return 0; | |
| if (str1.charAt(m - 1) == str2.charAt(n - 1)) | |
| return 1 + lcs(str1, str2, m - 1, n - 1); | |
| else | |
| return Math.max(lcs(str1, str2, m - 1, n), lcs(str1, str2, m, n - 1)); | |
| } | |
| //Iterative function | |
| public int lcs2(String str1, String str2) { | |
| int lcs[][] = new int[str1.length() + 1][str2.length() + 1]; | |
| for (int i = 0; i <= str1.length(); i++) { | |
| for (int j = 0; j <= str2.length(); j++) { | |
| if (i == 0 || j == 0) { | |
| lcs[i][j] = 0; | |
| } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) { | |
| lcs[i][j] = 1 + lcs[i - 1][j - 1]; | |
| } else { | |
| lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]); | |
| } | |
| } | |
| } | |
| return lcs[str1.length()][str2.length()]; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment