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

最长公共子序列-II

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

代码精简版

public static String LCS (String s1, String s2) {
        // write code here
        int n1 = s1.length(), n2 = s2.length();
        String[][] dp = new String[n1+1][n2+1];
        String res = "";
        for (int i=0;i<=n1;i++){
            for (int j=0;j<=n2;j++){
                // 所有的string都要初始化
                dp[i][j] = "";
                if (i == 0 || j == 0) continue;
                String c1 = s1.substring(i-1, i);
                String c2 = s2.substring(j-1, j);
                if (c1.equals(c2)){
                    dp[i][j] = dp[i-1][j-1] + c1;
                    if (dp[i][j].length() > res.length()){
                        res = dp[i][j];
                    }
                }else {
                    dp[i][j] = dp[i][j-1].length()>=dp[i-1][j].length() ? dp[i][j-1] : dp[i-1][j];
                }
            }
        }
        return res.equals("") ? "-1" : res;
    }
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-10 11:55
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务