比如说我有两个词。中国 和国人,(这个字符串是未知的,我只是举例),怎么判断这两个字符串中都包含相同的内容,在上述例子中相同的内容就是“国”?最好不用数组,求大神指导!
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。
public static int[][] LCS(String str1, String str2) {
int[][] opt = new int[str2.length() + 1][str1.length() + 1];
for (int i = 0; i <= str2.length(); i++) {
opt[i][0] = 0;
}
for (int j = 0; j <= str1.length(); j++) {
opt[0][j] = 0;
}
for (int j = 1; j <= str1.length(); j++) {
for (int i = 1; i <= str2.length(); i++) {
if (str2.charAt(i-1) == str1.charAt(j-1)) {
opt[i][j] = opt[i-1][j-1] + 1;
} else {
opt[i][j] = ( opt[i-1][j] >= opt[i][j-1] ? opt[i-1][j] : opt[i][j-1]);
}
}
}
return opt;
}
public static void print(int[][] opt, String X, String Y, int i, int j) {
if (i == 0 || j == 0) {
return;
}
if (X.charAt(i - 1) == Y.charAt(j - 1)) {
System.out.print(X.charAt(i - 1));
print(opt, X, Y, i - 1, j - 1); // don't put this line before the upper line. Otherwise, the order is wrong.
}else if (opt[i - 1][j] >= opt[i][j]) {
print(opt, X, Y, i - 1, j);
} else {
print(opt, X, Y, i, j - 1);}
}