[数据结构与算法] 动态规划解最长公共子串

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

示例1

" 12345"," 334"

" 34 "

备注：

1≤∣ str1∣ , ∣ str2∣≤5000

注意这题求的是最长公共子串，不是最长公共子序列，子序列可以是不连续的，但子串一

定是连续的。

思路

定义 dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最

长公共子串。如果要求dp[i][j]，也就是str1的第i个字符和str2的第j个字符为最后一个

元素所构成的最长公共子串，我们首先需要判断这两个字符是否相等。

如果不相等，那么他们就不能构成公共子串，也就是 dp[i][j]=0;

如果相等，我们还需要计算前面相等字符的个数，

其实就是 dp[i -1][j -1] ，所以 dp[i] [j]=dp[i -1][j -1]+1;

public class Main {
    public static void main(String[] args) {
        //System.out.println(lcs("34", "12345"));
        System.out.println(lcs("12345", "334"));
    }

    public static String lcs(String str1, String str2) {
        int maxLength = 0;// 记录最长公共子串的长度
        int maxLastIndex = 0;// 记录最长公共子串最后一个元素在字符串str1中的位置
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                    // dp[2][0] = 0, dp[2][1] = 0
                    // dp[3][1]= dp[2][0] + 1 = 1
                    // dp[3][2]= dp[2][1] + 1 = 1
                    // dp[4][3]= dp[3][2] + 1 = 2
                    // 如果遇到了更长的子串，要更新，记录最长子串的长度，
                    // 以及最长子串最后一个元素的位置
                    if (dp[i+1][j+1] > maxLength) {
                        maxLength = dp[i+1][j+1];
                        maxLastIndex = i;
                    }
                } else {
                    dp[i+1][j+1] = 0;
                }
            }
        }
        return str1.substring(maxLastIndex - maxLength + 1, maxLastIndex + 1);
    }

}

[数据结构与算法]动态规划解最长公共子串

描述

思路