最长公共子串和最长公共子序列的区别

  • 两个字符串的“最值”问题，可以使用二维DP的思路。之前解的最长公共子序列不要求字符之间连续，只需要相对位置不变即可，但是最长公共子串要求所有字符连续。
  • 如何在代码中体现字符连续这一逻辑呢？这需要改变二维DP数组的定义，之前的最长公共子序列的二维DP数组存放的是s1字符串以第i个字符结尾的子串和s2字符串以第j个字符结尾的子串的最长公共子序列长度，这次的二维DP数组存放的是s1字符串的第i个字符和s2字符串的第j个字符为最后一个元素所构成的最长公共子串长度。
  • 由于s1字符串的第i个字符和s2字符串的第j个字符为最长公共子串的最后一个字符，那么久可以保证前面的字符跟s1字符串的第i个字符和s2字符串的第j个字符是连续的。

最小子问题

当s1和s2两个字符串任意一个字符串长度为0时，即为空字符串时，两者都不可能有共同子串，体现在二维DP表中为i或j为0时DP[i][j]=0，因此初始状态可以视为当s1或者s2长度为0时的状态，此时公共子串长度都为0。

如何思考状态转移方程？

二维DP数组的定义已经变成了存放s1字符串的第i个字符和s2字符串的第j个字符为最后一个元素所构成的最长公共子串长度，则要求dp[i][j]，首先要判断这两个字符是否相等：

  • 如果s1字符串的第i个字符和s2字符串的第j个字符相等，那么这两个字符包含在公共子串内，此时dp[i][j] = 1+dp[i-1][j-1]。
  • 如果s1字符串的第i个字符和s2字符串的第j个字符相等，那么他们就不能构成公共子串，此时dp[i][j] = 0。

如何获得最长公共子串？

在构建dp表的过程中同时记录最长公共子串长度和最长公共子串的结束位置，最后再对字符串进行截取即可。

/*
 * @Author: LibraStalker **********
 * @Date: 2023-03-26 16:26:51
 * @FilePath: BM66-最长公共子串.js
 * @Description: 
 */

/**
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
 */
function LCS( str1 ,  str2 ) {
    // write code here
    const str1DPLength = str1.length + 1;
    const str2DPLength = str2.length + 1;
    const dp = Array.from(new Array(str1DPLength), () => new Array(str2DPLength).fill(0));
    let maxCommonLength = 0;
    let endIndex = -1;

    for (let i = 1; i <= str1.length; ++i) {
        for (let j = 1; j <= str2.length; ++j) {
            if (str1[i-1] === str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (maxCommonLength < dp[i][j]) {
                    maxCommonLength = dp[i][j];
                    endIndex = i - 1;
                }
            }
            else {
                dp[i][j] = 0;
            }
        }
    }

    return maxCommonLength === 0 ? "-1" : str1.substring(endIndex-maxCommonLength+1, endIndex+1);
}

module.exports = {
    LCS : LCS
};