# 14. Longest Common Prefix 最长公共前缀

• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客：http://fuxuemingzhu.cn/open in new window
• 个人公众号：负雪明烛
• 本文关键词：prefix, 公共前缀，题解，leetcode, 力扣，Python, C++, Java

@TOC

## # 题目描述

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

``````Input: ["flower","flow","flight"]
Output: "fl"
``````

Example 2:

``````Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
``````

Note:

• All given inputs are in lowercase letters a-z.

## # 解题方法

### # 遍历前缀子串

``````class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if strs == None or len(strs) == 0:
return ""
def is_common(prefix, strs):
return all(str.startswith(prefix) for str in strs)
for i in xrange(len(strs[0])):
pre = strs[0][:i + 1]
print pre
if is_common(pre, strs):
else:
break
``````

### # 使用set

``````class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs: return ""
pre = ""
_len = min(len(s) for s in strs)
for i in range(1, _len + 1):
if len(set(s[:i] for s in strs)) == 1:
pre = strs[0][:i]
return pre
``````

### # 遍历最短字符串

``````class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs: return ""
pre = min(strs, key = len)
for i, c in enumerate(pre):
for word in strs:
if word[i] != c:
return pre[:i]
return pre
``````

C++版本如下：

``````class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) return "";
string pre = strs[0];
for (auto word : strs){
if (word.size() < pre.size()){
pre = word;
}
}
for (int i = 0; i < pre.size(); ++i){
for (auto word : strs){
if (word.at(i) != pre.at(i)){
return pre.substr(0, i);
}
}
}
return pre;
}
};
``````

### # 排序

``````class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs: return ""
strs.sort()
size = min(len(strs[0]), len(strs[-1]))
i = 0
while i < size and strs[0][i] == strs[-1][i]:
i += 1
return strs[0][:i]
``````

C++代码如下：

``````class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
sort(strs.begin(), strs.end());
int size = min(strs[0].size(), strs.back().size());
int i = 0;
while (i < size && strs[0].at(i) == strs.back().at(i)){
++i;
}
return strs[0].substr(0, i);
}
};
``````

## # 日期

2017 年 8 月 25 日 2018 年 11 月 24 日 —— 周日开始！一周就过去了～