Lintcode DP Longest Common Substring/Subsequence
18 Dec 2015###Task1 Given two strings, find the longest common substring.
Return the length of it.
Have you met this question in a real interview? Yes Example Given A = “ABCD”, B = “CBCE”, return 2.
Note The characters in substring should occur continuously in original string. This is different with subsequence.
Challenge O(n x m) time and memory.
###Java ####DP
public class Solution {
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
// write your code here
if (A == null || B == null || A.length() == 0 || B.length() == 0) {
return 0;
}
int n = A.length();
int m = B.length();
int local[][] = new int[n + 1][m + 1];
int global[][] = new int[n + 1][m + 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if (A.charAt(i - 1) == B.charAt(j - 1)) {
local[i][j] = local[i - 1][j - 1] + 1;
} else {
local[i][j] = 0;
}
global[i][j] = Math.max(local[i][j], Math.max(global[i - 1][j], global[i][j - 1]));
}
}
return global[n][m];
}
}
###Points
- DP
- Global + local style: similar to maximum subarray.
###Task2 Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.
Have you met this question in a real interview? Yes Example For “ABCD” and “EDCA”, the LCS is “A” (or “D”, “C”), return 1.
For “ABCD” and “EACB”, the LCS is “AC”, return 2.
###Java
public class Solution {
/**
* @param A, B: Two strings.
* @return: The length of longest common subsequence of A and B.
*/
public int longestCommonSubsequence(String A, String B) {
// write your code here
if (A == null || B == null || A.length() == 0 || B.length() == 0) {
return 0;
}
int n = A.length();
int m = B.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
}
}
return dp[n][m];
}
}
###Points
- Diff: substring needs to be continuous.