开发者社区云计算文章正文

两个串最长公共子序列的长度：

2017-11-21 882

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： public class Main { //求两个串最长公共子序列的长度 //abcdef abc abd bdf public static int f(String s1,String s2){ if(s1.

public class Main {
//求两个串最长公共子序列的长度
//abcdef abc abd bdf
public static int f(String s1,String s2){
if(s1.length()==0||s2.length()==0){
return 0;
}
/**
* 主体部分
*/
if(s1.charAt(0)==s2.charAt(0)){ //如果头相同
return f(s1.substring(1),s2.substring(1))+1; //在交给下级的比较结果中加1
}else{
return Math.max(f(s1.substring(1),s2),f(s1,s2.substring(1))); //返回：max的选择执行，谁大执行谁
//执行方式（降低规模！！！）：谁大切谁，轮流切
}
}
/**
* 主体逻辑：
* 1.比较第一个，相同就加1继续执行（过程）
* 2.不同就去掉长的头元素，继续比较（变化）
* 3.一直到有一方为0，返回0种情况（出口）
* @param args
*/
public static void main(String[] args) {
int k=f("fabcdk","xbacd");
System.out.println(k);
}
}