求两个字符串的最长公共子串(字母可以不紧邻,但是顺序不变)
不知道为什么笔试总是遇到这些题目,看来经典算法,大家都喜欢啊,这个是LCS问题,动态规划。
问题:求两个字符串的最长公共子串,字母可以不相邻,但是顺序不变
代码:
public class lcs {
public static void LCS_Print(String str1, String str2) {
int length1 = str1.length();
int length2 = str2.length();
int list[][] = new int[length1 + 1][length2 + 1];//初始全为0
int i;//行
int j;//列
// 标记
for (i = length1 - 1; i >= 0; i--) {
for (j = length2 - 1; j >= 0; j--) {
if (str1.charAt(i) == str2.charAt(j)) { //相同
list[i][j] = list[i + 1][j + 1] + 1;
} else {//不同
list[i][j] = Math.max(list[i + 1][j], list[i][j + 1]);
}
}
}
// 计算lcs
i = 0;
j = 0;
while (i < length1 && j < length2) {
if (str1.charAt(i) == str2.charAt(j)) {//斜着走
System.out.print(str1.charAt(i));
i++;
j++;
} else if (list[i + 1][j] >= list[i][j + 1]) {//向下走
i++;
} else{//向左走
j++;
}
}
System.out.println();
}
public static void main(String[] args) {
String str1 = "abcddeesdd";
String str2 = "asadaaddss";
lcs.LCS_Print(str1, str2);
}
}