题解 | #最长公共子串#

动态规划

按照动态规划的思路进行思考，得到状态转移方程：
dp[i][j] = dp[i-1][j-1] + 1

//     public String LCS (String str1, String str2) {
//         // write code here
//         int[][] dp = new int[str1.length()+1][str2.length()+1];
//         int max = 0;
//         int position = 0;

//         for (int i = 1; i < str1.length()+1; i++) {
//             for (int j = 1; j < str2.length()+1; j++) {
//                 if (str1.charAt(i-1) == str2.charAt(j-1)) {
//                     dp[i][j] = dp[i-1][j-1] + 1;
//                     if (dp[i][j] > max) {
//                         max = dp[i][j];
//                         position = j;
//                     }
//                 }
//             }
//         }
//         return max == 0 ? "-1" : str2.substring(position-max, position);
//     }

动态规划优化

空间复杂度： O(2m)
时间复杂度： O(mn)

    public String LCS (String str1, String str2) {
        // write code here
        int l = str1.length() > str2.length() ? str1.length() : str2.length();
        int[][] dp = new int[2][l+1];
        int max = 0;
        int position = 0;

        for (int i = 1; i < str1.length()+1; i++) {
            for (int j = 1; j < str2.length()+1; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    // 获取上一层节点的值
                    dp[i%2][j] = dp[i%2 == 0 ? 1 : 0][j-1] + 1;
                    if (dp[i%2][j] > max) {
                        max = dp[i%2][j];
                        position = j;
                    }
                } else {
                    dp[i%2][j] = 0;
                }
            }
        }

        return max == 0 ? "-1" : str2.substring(position-max, position);
    }