> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/1-200/14.-zui-chang-gong-gong-qian-zhui.md).

# 14. 最长公共前缀

<https://leetcode-cn.com/problems/longest-common-prefix/submissions/>

## 解法一：水平搜索

这题与最长公共子串，最长公共子序列的区别在于另两者都是两个串之间的比对，而本题是多个串匹配，限制更多，相互影响，只要有**两个串**之间不存在公共，那所有串都不存在。&#x20;

先找strs\[0]和strs\[1]的共同**前缀**（注意前缀必须是**从头开始**的连续子串），以strs\[0]为基准前缀，在strs\[1]中找，若不存在，前缀**尾部**截去一个字符，成为新的前缀，直到prefix为空串。

以此类推，在所有串中找一遍。

```python
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        n = len(strs)
        if n == 0:  return ""
        prefix = strs[0]    #前缀
        for i in range(1, n):
            while strs[i].find(prefix) != 0:    #若找不到前缀，前缀去尾
                prefix = prefix[:len(prefix)-1]
        return prefix
```

## 解法二：垂直搜索

```python
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        n = len(strs)
        if n == 0:  return ""
        #以0号串为基准
        for i in range(len(strs[0])):    #对基准的每一位
            for j in range(1, n):    #比对所有串
                #若找到一位与基准串不符，返回（前一个条件为了防越界）
                if len(strs[j]) == i or strs[j][i] != strs[0][i]:
                    return strs[0][:i]
        return strs[0]    #都符合，则基准就是所求
```

与上面水平搜索的区别在于，水平是每个串之间比对一遍，垂直是以strs\[0]为基准，对其每个字符，在所有串之间比对。好处在于如果有一个最短串位于strs\[n-1]，长度为p，水平搜索就要遍历所有的串，复杂度为`len(strs[0] + strs[1] + ... + strs[n-1])`。而垂直搜索最多只遍历所有的串的前p位，复杂度为`p * n = len(strs[n-1]) * n`，也就是说不用遍历所有的情况。