题解 | #最长公共子串# | JAVA | 动态规划+备忘录

最长公共子序列-II

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

超越8%的人, 还有待提升 , 简单易懂

public class Solution {
   public String LCS (String s1, String s2) {
         //备忘录,增加效率。 不然过不了。 
        meno = new String[s1.length()][s2.length()];
        // 填充值
        for (int i = 0; i < s1.length(); i++) {
            Arrays.fill(meno[i],"-1");
        }
        //动态规划找最大
        String result = dp(s1, 0, s2, 0);
        return result.length() == 0 ? "-1" : result;
    }

    //备忘录,增加效率。 不然过不了。 
    String[][] meno;

    public String dp(String s1, int i, String s2, int j) {
        //base case, 递归出口
        if (s1.length() == i || s2.length() == j) {
            return "";
        }
        // 避免重复计算
        if (!meno[i][j].equals("-1")) {
            return meno[i][j];
        }
         //状态转义
        if (s1.charAt(i) == s2.charAt(j)) {
            //如果等于 直接赋值 , s1 , s2同时增加一个长度
            meno[i][j] = s2.charAt(j) + dp(s1, i + 1, s2, j + 1);
        } else {
            // s1 增加一个长度
            String dp = dp(s1, i + 1, s2, j);
            //  s2增加一个长度
            String dp1 = dp(s1, i, s2, j + 1);
            // 谁长统计谁 
            String temp = dp.length() > dp1.length() ? dp : dp1;
            meno[i][j] = temp;
        }
        return meno[i][j];
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 14:10
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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