2021/1/25 最长公共子串

问题描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。

示例

输入

"1AB2345CD","12345EF"

返回值

"2345"

解题思路

使用了正则表达式法和动态规划法，都自测通过，但是不知道为什么在这里都过不了；
（2021/4/21补充：今天重新做这道题，发现可以通过了，果然是当时牛客系统有问题）

1. 正则表达式方法，不多赘述；
2. 典型的动态规划问题，解题思路与2021/1/21 藏宝图类似。系统传入两个字符串，所以我们首先可以考虑二维数组，再考虑滚动的一维数组；
3. 我们可以设二维数组 dp[i][j] 的行表示原字符串的每一个字符，列表示子串的每一个字符，dp[i][j] 表示原字符串第 i 个字符与子串第 j 个字符是否匹配，匹配则 dp[i][j] = 1。

Java代码实现

public class Solution {

    // 1. 正则表达式方法
    public String LCS (String str1, String str2) {
        String regex = "[" + str2 + "]+";
        Pattern pattern = Pattern.compile(regex);
        Matcher matcher = pattern.matcher(str1);
        String result = "";
        while (matcher.find()) {
            String newResult = matcher.group();
            if (newResult.length() > result.length()) {
                result = newResult;
            }
        }
        return result.length() != 0 ? result : "-1";
    }


     // 2. 动态规划方法1
     public String LCS (String str1, String str2) {
        if (isEmpty(str1) || isEmpty(str2)) return "-1";
        int rowLen = str1.length() + 1;
        int colLen = str2.length() + 1;
        int[][] dp = new int[rowLen][colLen];

        int maxIndex = 0;
        int maxLength = 0;
        for (int i = 1; i < rowLen; ++i) {
            for (int j = 1; j < colLen; ++j) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if (dp[i][j] > maxLength) {
                        maxIndex = i;
                        maxLength = dp[i][j];
                    }
                }
            }
        }
        return str1.substring(maxIndex - maxLength, maxIndex);
    }

    private boolean isEmpty(String str) {
        return str == null || str.length() == 0;
    }

    // 3.动态规划方法2（容易理解一点，但是代价比较大）
    public String LCS (String str1, String str2) {
        int max = 0;    // 记录最长的子串长度
        String res = "";    // 记录最长公共子串
        int rowLen = str1.length();
        int colLen = str2.length();
        String[][] dp = new String[rowLen + 1][colLen + 1];
        init(dp);
        for (int i = 1; i < rowLen + 1; ++i) {
            for (int j = 1; j < colLen + 1; ++j) {
                char cur = str2.charAt(j - 1);
                if (str1.charAt(i - 1) == cur) {
                    dp[i][j] = dp[i - 1][j - 1] + String.valueOf(cur);
                    if (max < dp[i][j].length()) {
                        max = dp[i][j].length();
                        res = dp[i][j];
                    }
                }
            }
        }
        return res;
    }

    private void init(String[][] arr) {
        for (int i = 0; i < arr.length; ++i) {
            for (int j = 0; j < arr[0].length; ++j) {
                arr[i][j] = "";
            }
        }
    }
}