题目
两个字符串的最长公共子串的长度
例如：
“ABCDGH”和“AEDFHR”的最长公共子串为“ADH”，长度为3。
“AGGTAB”和“GXTXAYB”的最长公共子串为“GTAB”，长度为4。
解析
两个字符串的最长公共子串是一个常见的问题，《算法导论》中介绍动态规划的一个示例。假设两个字符串为str1和str2，遍历的下标分别为i1和i2。二维数组array[][]存储结果。
- 如果i1=0或者i2=0，最长公共子串长度为0。
- 如果str1[i1]=str2[i2]，字符为Z，最长公共子串就是str1[0~i1-1]和str2[0~i2-1]两个子串的最长公共子串加上Z。
- 如果str1[i1]不等于str2[i2]，最长公共子串可能是str1[0~i1]和str2[0~i2-1]，或者是str1[0~i1-1]和str2[0~i2]中的最长公共子串。
代码
public int lengthOfLCS(String str1, String str2){
if (null == str1 || str1.length() == 0){
return 0;
}
if (null == str2 || str2.length() == 0){
return 0;
}
int length1 = str1.length();
int length2 = str2.length();
//array[i1][i2]记录两个子串的最长公共子串长度
int[][] array = new int[length1 + 1][length2 + 1];
//动态规划，计算二维数组其他位置的值
for (int i1 = 1; i1 < length1 + 1; i1++){
for (int i2 = 1; i2 < length2 + 1; i2++){
//如果两个字符相同
if (str1.charAt(i1 - 1) == str2.charAt(i2 - 1)){
//最长公共子串长度
array[i1][i2] = array[i1 - 1][i2 - 1] + 1;
} else {//如果两个字符不同
//最长公共子串长度为包含当前其中一个字符的公共子串的最大值
array[i1][i2] = Math.max(array[i1 - 1][i2], array[i1][i2 - 1]);
}
}
}
//返回两个字符串的最长公共子串的长度
return array[length1][length2];
}
