Javascript 中最长的常见前缀和后缀[已关闭]

Question

如果我们得到类似的字符串

["charcoal","chimnicoal","chestarcoal"]

现在我们怎么找到这里，因为这里前缀也匹配，后缀也匹配......那么我们如何用javascript编写代码呢？

if (strs.length === 0) return "";
let output = strs[0];
for (let i = 1; i < strs.length; i++) {
    let j = 0;
    while (j < output.length && j < strs[i].length && output[j] === strs[i][j]) {
        j++;
    }
    output = output.slice(0, j);
}
return output;

但是它不起作用......

Answer 1

一个简单的解决方案是迭代单词并与邻居的公共前缀和后缀进行比较：

const input = ["charcoal","chimnicoal","chestarcoal"];

let maxPrefix = -Infinity, maxSuffix = Infinity;
let prevPrefix = input[0], prevSuffix = input[0];

for(let i = 1; i < input.length; i++){
  const curr = input[i];
  let j = 0, k = -1;
  for(; j < curr.length && j < prevPrefix.length; j++){
    if(curr[j] !== prevPrefix[j]) break;
  }
  for(; -k < curr.length+1 && -k < prevSuffix.length+1; k--){
    if(curr.at(k) !== prevSuffix.at(k)) break;
  }
  prevPrefix = prevPrefix.slice(0, j);
  prevSuffix = k === -1 ? '' : prevSuffix.slice(k + 1);
}

console.log([prevPrefix, prevSuffix]);