Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.
Example
For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.
For "ABCD" and "EACB", the LCS is "AC", return 2.
分析：
典型的DP。
public class Solution {
/**
* @param A, B: Two strings.
* @return: The length of longest common subsequence of A and B.
*/
public int longestCommonSubsequence(String str1, String str2) {
if (str1 == null || str2 == null) return ;
int[][] opt = new int[str2.length() + ][str1.length() + ];
for (int j = ; j <= str1.length(); j++) {
for (int i = ; i <= str2.length(); i++) {
if (i == || j == ) {
opt[i][j] = ;
} else if (str2.charAt(i-) == str1.charAt(j-)) {
opt[i][j] = opt[i-][j-] + ;
} else {
opt[i][j] = Math.max(opt[i-][j], opt[i][j-]);
}
}
}
return opt[str2.length()][str1.length()];
}
}
Longest Common Substring
Given two strings, find the longest common substring.
Return the length of it.
Notice
The characters in substring should occur continuously in original string. This is different with subsequence.
Example
Given A = "ABCD", B = "CBCE", return 2.
分析：
从头比到尾呗。
public class Solution {
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
if (A == null || B == null || A.length() == || B.length() == ) return ;
int max = ;
for (int i = ; i < B.length(); i++) {
for (int j = ; j < A.length(); j++) {
int incr = ;
while (i + incr < B.length() && j + incr < A.length() && (B.charAt(i + incr) == A.charAt(j + incr))) {
incr++;
max = Math.max(max, incr);
}
}
}
return max;
}
}
Longest Common Prefix
Given k strings, find the longest common prefix (LCP).
Example
For strings "ABCD", "ABEF" and "ACEF", the LCP is "A"
For strings "ABCDEFG", "ABCEFG" and "ABCEFA", the LCP is "ABC"
分析：
取出第一个string和剩余的string相比即可。
public class Solution {
/**
* @param strs: A list of strings
* @return: The longest common prefix
*/
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == ) return "";
if (strs.length == ) return strs[];
StringBuilder sb = new StringBuilder();
for (int j = ; j < strs[].length(); j++) {
for (int i = ; i < strs.length; i++) {
if (j >= strs[i].length() || strs[i].charAt(j) != strs[].charAt(j)) {
return sb.toString();
}
}
sb.append(strs[].charAt(j));
}
return sb.toString();
}
}