描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。

示例1

输入：
"1AB2345CD","12345EF"

返回值：
"2345"

思路

首先这道题要的是最长公共子串，而不是子序列；子序列不需要连续，而子串要求要连续的。
这道题可以利用动态规划的思想来解决。

1. 创建一个 dp[][] 二维数组,比如：dp[1][1] 代表 两个字符串下标为 1 的最长公共子串长度。
2. 然后就遍历两个字符串，找到所有下标对应的最大公共子串长度
3. 最后再找到最长的那个公共子串

AC 代码

public String LCS (String str1, String str2) {
        // write code here
        if (str1 == null || str1.length() < 1 || str2 == null || str2.length() < 1) {
            return "";
        }
        int length1 = str1.length();
        int length2 = str2.length();
        // 用来存储两个字符串下标对应的公共子串的长度
        int[][] dp = new int[length1][length2];
        // 最大公共子串的长度
        int maxLength = 0;
        // 最大长度的 str 字符串下标值
        int maxIndex = 0;
        // 初始化dp数组，当两个字符串第一个字符相等时，dp[0][0] = 1, 否则为 0
        if(str1.charAt(0) == str2.charAt(0)) {
            dp[0][0] = 1;
            maxLength = 1;
            maxIndex = 1;
        }
        // 双层for 循环遍历
        for (int i = 1; i < length1; i ++) {
            char ch1 = str1.charAt(i);
            for (int j = 1; j < length2; j ++) {
                char ch2 = str2.charAt(j);
                // 如果两个字符相等
                if (ch1 == ch2) {
                    // 该位置的长度为 上次公共子串长度 + 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    // 如果本次公共子串长度最大，则以这次子串为最优解
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        maxIndex = i + 1;
                    }

                }
            }
        }
        // 确定了最大子串长度以及子串末尾下标位置，对str1进行截取
        return maxLength > 0 ? str1.substring(maxIndex - maxLength, maxIndex) : "";
    }

时间复杂度：O(m * n), m 是 str 的长度，n 是 str2 的长度
空间复杂度：O(m * n), 创建了 二维数组

最后

这道题运用动态规划的方式来解决。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。