JavaScript 中最长的通用前缀

Question

我正在尝试解决 Leet Code 挑战14. 最长的常见前缀：

编写一个函数来查找字符串数组中最长的公共前缀字符串。

如果没有公共前缀，则返回空字符串""。

示例1：

Input: strs = ["flower", "flow", "flight"]
Output: "fl"

示例2：

Input: strs = ["dog", "racecar", "car"]
Output: ""

说明：输入字符串之间没有公共前缀。

限制条件：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]仅由小写英文字母组成。

我的解决方案：

Input: strs = ["flower", "flow", "flight"]
Output: "fl"

输出：f

如何迭代每个字符并检查它是否相同，然后继续下一个，如果失败则返回最长的公共前缀？

Answer 1

由于最长的公共前缀必须出现在数组的每个字符串中，因此您可以迭代长度并检查所有单词在该索引处是否具有相同的字符，直到找到差异

function prefix(words){
  // check border cases size 1 array and empty first word)
  if (!words[0] || words.length ==  1) return words[0] || "";
  let i = 0;
  // while all words have the same character at position i, increment i
  while(words[0][i] && words.every(w => w[i] === words[0][i]))
    i++;
  
  // prefix is the substring from the beginning to the last successfully checked i
  return words[0].substr(0, i);
}

console.log(1, prefix([]));
console.log(2, prefix([""]));
console.log(3, prefix(["abc"]));
console.log(4, prefix(["abcdefgh", "abcde", "abe"]));
console.log(5, prefix(["abc", "abc", "abc"]));
console.log(6, prefix(["abc", "abcde", "xyz"]));

Answer 2

一些问题：

• return您的内部循环将在第一次迭代时遇到 a 。这意味着您的循环将永远不会重复，并且返回值将始终是一个字符。

• 在循环中寻址strs[i+1]and是错误的strs[i+2]，因为这些索引将超出范围 ( >= strs.length)

您可以使用子字符串（前缀）比较（在一个操作中），而不是逐个字符地进行比较：这可能看起来很浪费，但由于这种比较发生在 JavaScript 代码“下方”，因此速度非常快（并且字符串大小限制为200 个字符，这样就可以了）。

该算法可以首先选择一个现有字符串作为前缀，然后在每次输入中存在不具有该字符串作为前缀的字符串时缩短它。最后，您将留下公共前缀。

最好从最短的字符串作为初始候选前缀，因为公共前缀肯定不能比它长。

var longestCommonPrefix = function(strs) {
    let prefix = strs.reduce((acc, str) => str.length < acc.length ? str : acc);
    
    for (let str of strs) {
        while (str.slice(0, prefix.length) != prefix) {
            prefix = prefix.slice(0, -1);
        }
    }
    return prefix;
};

let res = longestCommonPrefix(["flower","flow","flight"]);

console.log(res);