# NC127.最长公共子串

# 题目描述

TIP

标签：动态规划

关联企业：阿里巴巴、字节跳动、美团、腾讯、滴滴

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

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

示例1
输入："1AB2345CD","12345EF"
返回值："2345"

1
2
3

# 算法思路:

/**
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
 */
function LCS(str1, str2) {
  if (str1.length > str2.length) {
    [str1, str2] = [str2, str1];
  }
  let len = str1.length;
  let res = "";
  let maxLen = 0;
  for (let i = 0; i < len; i++) {
    let tempStr = str1.slice(i - maxLen, i + 1);
    if (str2.indexOf(tempStr) !== -1) {
      res = tempStr;
      maxLen++;
    }
  }
  return res;
}
module.exports = {
  LCS: LCS,
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

1、首先，函数会比较两个输入字符串的长度，如果第一个字符串的长度大于第二个字符串的长度，则交换两个字符串，确保第一个字符串较短。
2、然后，函数定义了三个变量：len表示较短字符串的长度，res用于保存最长公共子序列，maxLen用于记录当前已找到的最长公共子序列的长度。
3、接下来，函数通过一个循环遍历较短字符串的每个字符，依次尝试构建子串 tempStr，并检查该子串是否是第二个字符串的子序列（即是否存在于第二个字符串中）。
4、如果 tempStr 是第二个字符串的子序列，那么更新 res 为当前的 tempStr，并增加 maxLen。
5、最后，返回找到的最长公共子序列 res。