javascript - 一组字符串 JavaScript 中最长的公共(public)子字符串

Question

我试图在 JavaScript 的一组字符串中找到最长的公共(public)子字符串。

我的想法来自 Find the longest common starting substring in a set of strings

但我不只是在寻找凝视子串

因此，我继续执行以下操作:

我猜它按预期工作，但有 map 和 sort 的开销。

function longestCommonSubstring(array) {
    // Copy the array
    let arr = array.slice().sort();
    // For each individual string sort them 
    arr = arr.map(a => a.split('').sort().join(''));
    // Check the first and last string and check till chars match
    let a0 = arr[0],
        aLast = arr[arr.length -1],
        len = arr[0].length,
        i = 0;
    while(i < len && a0[i] === aLast[i]) i++;
    // return
    return a0.substring(0,i);
}

我做错了吗？能否以更有效的方式完成？

输入 ["abc","cxabgi"]

输出 ["ab"]

Answer 1

function longestCommonSubstring(array) {
  const sortedArray = [...array].sort();
  const firstItem = sortedArray[0];
  const lastItem = sortedArray[sortedArray.length - 1];
  const firstItemLength = firstItem.length;
  let i = 0;

  while (i < firstItemLength && firstItem.charAt(i) === lastItem.charAt(i)) {
    i++;
  }

  return firstItem.substring(0, i);
}