如何在数组集合中检测最长超字符串？当前结果不符合预期

你的原代码只是找出了所有数组的公共元素交集，所以得到了['l','b','a']（转成字符串就是'lbal'），但这不是连续的序列。要找所有数组都包含的最长连续子序列，可以按下面的思路来：

核心思路 #

1. 先把每个字符数组转成字符串，方便处理连续子串
2. 以最短的字符串为基准（最长公共子串不可能超过它的长度），生成它的所有可能连续子串，按长度从长到短排序
3. 逐个检查这些子串是否在所有其他字符串中存在，第一个匹配到的就是最长的目标子串

代码实现 #

const arr = [
  ['g', 'l', 'o', 'b', 'a', 'l'],
  ['b','a','l','l']
];

// 把字符数组转成字符串
const strs = arr.map(charArr => charArr.join(''));

// 找出最短的字符串，减少子串生成量
const shortestStr = strs.reduce((a, b) => a.length <= b.length ? a : b);

// 生成最短字符串的所有连续子串，按长度降序排序
const getAllSubstrings = (str) => {
  const substrs = new Set();
  for (let i = 0; i < str.length; i++) {
    for (let j = i + 1; j <= str.length; j++) {
      substrs.add(str.slice(i, j));
    }
  }
  return Array.from(substrs).sort((a, b) => b.length - a.length);
};

const allSubstrs = getAllSubstrings(shortestStr);

// 找出第一个在所有字符串中都存在的子串
const longestCommonSubstr = allSubstrs.find(substr => {
  return strs.every(str => str.includes(substr));
});

console.log(longestCommonSubstr); // 输出 'bal'

代码解释 #

• 转字符串：把每个字符数组拼接成完整字符串，比如['b','a','l','l']变成'ball'，方便用includes检查子串
• 选最短字符串：因为最长公共子串的长度不可能超过最短字符串的长度，这样能减少需要检查的子串数量，提升效率
• 生成子串：遍历最短字符串的所有起始和结束位置，生成所有可能的连续子串，用Set去重后按长度从长到短排序
• 匹配检查：逐个检查子串是否在所有字符串中存在，第一个符合条件的就是最长的公共连续子串

内容的提问来源于stack exchange，提问作者brad_fresh