public static int longestCommonSubsequence (String a, String b) { if (a == null || b == null || a.length() == 0 || b.length() == 0) return 0; int len1 = a.length(); int len2 = b.length(); int[][] lcs = new int[len1 + 1][len2 + 1]; lcs[0][0] = 0; for (int j = 0; j <= len2; j++) lcs[0][j] = 0; for (int i = 0; i <= len1; i++) lcs[i][0] = 0; for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (a.charAt(i - 1) == b.charAt(j - 1)) { lcs[i][j] = Math.max(Math.max(lcs[i - 1][j], lcs[i][j - 1]), lcs[i - 1][j - 1] + 1); } else { lcs[i][j] = Math.max(Math.max(lcs[i - 1][j], lcs[i][j - 1]), lcs[i - 1][j - 1]); } } } return lcs[len1][len2]; }
AdSense
Saturday, January 17, 2015
Longest Common Subsequence
Very typical 2D DP.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment