題目
兩個(gè)字符串的最長公共子串的長度
例如：
“ABCDGH”和“AEDFHR”的最長公共子串為“ADH”逆趋，長度為3盏阶。
“AGGTAB”和“GXTXAYB”的最長公共子串為“GTAB”晒奕，長度為4闻书。
解析
兩個(gè)字符串的最長公共子串是一個(gè)常見的問題，《算法導(dǎo)論》中介紹動(dòng)態(tài)規(guī)劃的一個(gè)示例脑慧。假設(shè)兩個(gè)字符串為str1和str2魄眉，遍歷的下標(biāo)分別為i1和i2。二維數(shù)組array[][]存儲(chǔ)結(jié)果闷袒。
- 如果i1=0或者i2=0坑律，最長公共子串長度為0。
- 如果str1[i1]=str2[i2]囊骤，字符為Z晃择，最長公共子串就是str1[0~i1-1]和str2[0~i2-1]兩個(gè)子串的最長公共子串加上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]記錄兩個(gè)子串的最長公共子串長度
int[][] array = new int[length1 + 1][length2 + 1];
//動(dòng)態(tài)規(guī)劃滑蚯，計(jì)算二維數(shù)組其他位置的值
for (int i1 = 1; i1 < length1 + 1; i1++){
for (int i2 = 1; i2 < length2 + 1; i2++){
//如果兩個(gè)字符相同
if (str1.charAt(i1 - 1) == str2.charAt(i2 - 1)){
//最長公共子串長度
array[i1][i2] = array[i1 - 1][i2 - 1] + 1;
} else {//如果兩個(gè)字符不同
//最長公共子串長度為包含當(dāng)前其中一個(gè)字符的公共子串的最大值
array[i1][i2] = Math.max(array[i1 - 1][i2], array[i1][i2 - 1]);
}
}
}
//返回兩個(gè)字符串的最長公共子串的長度
return array[length1][length2];
}
