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

超越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];
    }
}