获取最长公共前缀

题目

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

如果不存在公共前缀，返回空字符串 ""。

示例 1:
输入: ["flower","flow","flight"]
输出: "fl"

示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix

思路

0、初始化最长公共前缀为数组第一个字符串

1、求出数组长度 len

2、如果 len 等于零，说明为空数组，不可能有最长公共前缀，返回空

3、 遍历数组

(1) 对比当前最长公共前缀与每一个字符串是否有交集，没有的话，最长公共前缀截取该字符前面的字符串，继续下一个

(2) 若遍历完了，公共前缀为空，说明没有公共前缀，返回空，否则，返回当前最长公共前缀

题解

js 题解

const len = strs.length;
let lcp = strs[0];
if (len == 0) return '';
for (let i = 1; i < len; i++) {
  const prefixLen = strs[i].length;
  let j = 0;
  for (; j < lcp.length && j < prefixLen; j++) {
    if (lcp[j] != strs[i][j]) break;
  }
  lcp = lcp.substr(0, j);
  if (lcp === '') return lcp;
}
return lcp;

python 题解：

这个解法用到了 python 的一个独有的数据处理能力，把数组转置为矩阵，通过判断矩阵每行的重复数为 1，判别数组中的每个元素的公共前缀。有点曲径通幽处的感觉，很妙。

class Solution:
    def longestCommonPrefix(self, strs) -> str:
        if not strs:
            return ''
        r = []
        for item in zip(*strs):
            r.append(len(set(item)) == 1)
        r += [0]
        res = strs[0][:r.index(0)]
        return res

    def __init__(self, arr):
        for item in ex:
            print(self.longestCommonPrefix(item))

ex = [["dog", "racecar", "car"], ["flower", "flow", "flight"], []]
Solution(ex)