题解 | #最长公共子序列#

最长公共子序列

http://www.nowcoder.com/questionTerminal/6d29638c85bb4ffd80c020fe244baf11

public String LCS (String s1, String s2) {
//        设置状态变量dp[i][j]:表示下标为[0,i-1]的s1和下标为[0,j-1]的s2的最长公共子序列的大小
        int[][] dp=new int[s1.length()+1][s2.length()+1];

        for (int i=1;i<s1.length()+1;i++){
            for (int j=1;j<s2.length()+1;j++){
                if (s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;

                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }

        int len1=s1.length();
        int len2=s2.length();

        StringBuilder sb = new StringBuilder();

        while (len1>0&&len2>0){
            //如果两个位置的字符相等,直接添加进sb中
            if (s1.charAt(len1-1)==s2.charAt(len2-1)){
                sb.append(s1.charAt(len1-1));
                len1--;
                len2--;
            }else {//如果不相等,则要根据dp[][]来判断应该向哪个方向移动
                if (dp[len1][len2-1]>dp[len1-1][len2]){//说明len2方向的有更多相同的字符,所以len2--
//                    说明dp[len1][len2]==dp[len1][len2-1],
                    len2--;
                }else {
                    len1--;
                }
            }
        }


        if (sb.length() == 0) return "-1";
        return sb.reverse().toString();
    }
全部评论

相关推荐

05-07 17:58
门头沟学院 Java
wuwuwuoow:1.简历字体有些怪怪的,用啥写的? 2.Redis 一主二从为什么能解决双写一致性? 3.乐观锁指的是 SQL 层面的库存判断?比如 stock > 0。个人认为这种不算乐观锁,更像是乐观锁的思想,写 SQL 避免不了悲观锁的 4.奖项证书如果不是 ACM,说实话没什么必要写 5.逻辑过期时间为什么能解决缓存击穿问题?逻辑过期指的是什么 其实也没什么多大要改的。海投吧
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客企业服务