如何在字符串数组中找到最长的公共前缀？

Question

我正在尝试使用 .every 方法解决这个问题，但它没有返回 true，因此它没有添加到我的字符串中，我不确定为什么。

var longestCommonPrefix = function(arr) {
  if (arr.length === 0) {
    return undefined;
  }
  let result = '';
  for (let i = 0; i < arr.length; i++) {
    if (arr.every(x => arr[i].charAt(i) === x)) {
      result += arr[i].charAt(i);
    }
  }
  return result
}

console.log(longestCommonPrefix(["flower", "flow", "flight"])); //fl

Answer 1

您需要迭代 one 字符串，而不是整个数组：检查字符串的第一个字符是否存在于各处，然后检查第二个字符，依此类推：

var longestCommonPrefix = function(arr) {
  if (arr.length === 0) {
    return undefined;
  }
  let result = '';
  for (let i = 0; i < arr[0].length; i++) {
    if (arr.every(x => x.charAt(i) === arr[0][i])) {
      result += arr[i].charAt(i);
    } else break;
  }
  return result;
}

console.log(longestCommonPrefix(["flower", "flow", "flight"])); //fl

Answer 2

您对

Array.every

的使用是正确的。您想要检查数组中的每个字符串在位置

i

处是否具有相同的字符。我认为当您将参数命名为

x

时，您会感到困惑，而它实际上是一个字符串:)

var longestCommonPrefix = function(words) {
  if (words.length === 0) {
    return "";
  }
  
  const letters = [];
  const lengthOfShortestWord = Math.min(...words.map(word => word.length));
  
  for (let i = 0; i < lengthOfShortestWord; i++) {
    const char = words[0][i];
    if (words.every(word => word[i] === char)) {
      letters.push(char);
    } else {
      break;
    }
  }
  return letters.join("");
}

console.log(longestCommonPrefix(["flower", "flow", "flight"])); //fl

Answer 3

除非我弄错了，否则最长的前缀永远不会大于数组中最小的字符串。

在这种情况下，

"fl"

既是最小字符串又是最长公共前缀：

["flower", "fl", "flight"]

所以从找到

arr

中最小的字符串开始：

let [sm] = [...arr].sort((a, b) => a.length - b.length);

然后检查

arr

中的所有字符串是否以

sm

开头：

arr.every(str => str.startsWith(sm));

如果不是这种情况，请将

sm

缩短一个字符：

sm = sm.slice(0, -1);

继续前进，直到最终找到最长的前缀或

sm

变成空字符串：

const prefix = arr => {
  let [sm] = [...arr].sort((a, b) => a.length - b.length);
  while (sm && !arr.every(str => str.startsWith(sm))) sm = sm.slice(0, -1);
  return sm;
};

Answer 4

最重要的是@CertainPerformance所说的：“你需要迭代一个字符串”并且通过这个逻辑你可以使用这样的东西：

var longestCommonPrefix = (strs) => {
    let lettersInCommon = ''

    for (let i = 0; i < strs[0].length; i++) {
        if (strs.every(str => str.charAt(i) === strs[0][i]))
            lettersInCommon += strs[0].charAt(i)
    }
    return lettersInCommon
}

console.log(longestCommonPrefix(["flower","flow","flight"]))