怎样求字符串数组的最长公共前缀？

简答

给一组字符串，比如 ["flower", "flow", "flight"]，找出它们开头共同的那一段，这里是 "fl"；没有共同开头，比如 ["dog", "racecar", "car"]，就返回空字符串。

最直接的做法是逐个缩短。先假设第一个字符串整个都是公共前缀，然后拿它和第二个、第三个字符串比：对方不以它开头，就把它最后一个字符去掉，再比，直到对方以它开头为止。所有字符串比完，剩下的就是答案。

另一种是按列比较。从第 0 个字符开始，检查每个字符串在这个位置上的字符是否和第一个字符串相同，全都相同就看下一列，一旦有不同或者某个字符串已经到头，前面的部分就是答案。按列比较的好处是只要遇到最短的那个字符串，就能提前停下。

要注意空字符串和只有一个字符串的边界。数组里有空字符串时答案一定是空串；只有一个字符串时答案就是它自己。题目保证数组至少有一个元素，所以直接读 strs[0] 不会出错。

两种写法

longestCommonPrefix 是逐个缩短的写法，longestCommonPrefixByColumn 是按列比较的写法。

function longestCommonPrefix(strs) {
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i += 1) {
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.slice(0, -1);
    }
    if (prefix === '') return '';
  }
  return prefix;
}

function longestCommonPrefixByColumn(strs) {
  const first = strs[0];
  for (let i = 0; i < first.length; i += 1) {
    for (let j = 1; j < strs.length; j += 1) {
      if (i === strs[j].length || strs[j][i] !== first[i]) {
        return first.slice(0, i);
      }
    }
  }
  return first;
}

console.log(longestCommonPrefix(['flower', 'flow', 'flight'])); // fl
console.log(JSON.stringify(longestCommonPrefix(['dog', 'racecar', 'car']))); // ""
console.log(longestCommonPrefixByColumn(['flower', 'flow', 'flight'])); // fl
console.log(longestCommonPrefixByColumn(['ab', 'a'])); // a
console.log(JSON.stringify(longestCommonPrefixByColumn(['', 'b']))); // ""
console.log(longestCommonPrefixByColumn(['alone'])); // alone

先看逐个缩短。prefix 一开始是 "flower"，和 "flow" 比时，"flow" 不以 "flower" 开头，于是去掉一个字符变成 "flowe"，还不行，再去掉一个变成 "flow"，满足了。再和 "flight" 比，一路缩到 "fl" 才满足。比完所有字符串，答案就是 "fl"。

while 循环会不会停不下来？不会。空字符串是任何字符串的前缀，"任意".startsWith('') 一定是 true，所以 prefix 最多缩到空串就会停。循环后面判断 prefix === '' 是为了提前结束，后面的字符串不用再比了。

再看按列比较。外层循环走第一个字符串的每个位置 i，内层检查其他字符串的第 i 个字符。i === strs[j].length 表示这个字符串已经到头，比如 ['ab', 'a'] 在 i = 1 时，"a" 已经没有第 1 个字符，就返回 "a"。第一个字符串走完都没有返回，说明它整个都是公共前缀，比如只有一个元素 ['alone'] 时，内层循环一次都不执行，直接返回 "alone"。

复杂度怎么算

设 S 是所有字符串的字符数之和。按列比较时，每个字符最多被比较一次，所以时间是 O(S)，最好情况下第一列就不同，马上返回。逐个缩短的写法里，startsWith 和 slice 每次都要扫描和复制字符串，最坏情况下，比如所有字符串都相同，总比较量也是 O(S) 的量级，但缩短过程会多做一些重复比较。两种写法都只用常数个额外变量，除了返回的字符串之外，额外空间是 O(1)。

还有一种办法是先把数组按字典序排序，然后只比较第一个和最后一个字符串的公共前缀，因为排序后差异最大的两个就在两端。但排序本身要 O(n log n) 次字符串比较，比上面两种都慢，面试里说思路就够了。

前缀查询如果要反复进行，比如搜索框的输入提示，就不适合每次都这样扫一遍，可以用前缀树，见《搜索建议什么时候适合用 Trie？前缀树怎样处理重复词和 Unicode？》。

常见追问

为什么按列比较时要判断字符串是否到头？

因为第一个字符串不一定是最短的。如果不判断，strs[j][i] 越界时会得到 undefined，和 first[i] 不相等，碰巧也会返回正确结果，但这是依赖越界的行为，写出 i === strs[j].length 意图更清楚。

能用二分查找做吗？

能。公共前缀的长度在 0 到最短字符串长度之间，可以二分这个长度，每次检查所有字符串在这个长度上的前缀是否相同。时间是 O(S · log m)，m 是最短字符串的长度，比按列比较还多了一个 log，所以一般不用。

题目里的字符串都是小写字母，有什么影响？

题目约束非空字符串只包含小写英文字母，所以按下标逐个比较字符是安全的。如果输入里有 emoji 这类由两个 UTF-16 码元组成的字符，按下标截出来的前缀可能把一个字符切成两半，相关原因见《为什么字符串 length 不一定等于用户看到的字符数？》。