0. 题目
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.
1. C++版本
首先想到的测试用例如下:
思想:对于一系列字符串,可以先确定长度minLen最小的字符串,然后依次minLen比较每个字符串的是不是一样
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty())
return "";
int minLen = strs[0].size();
string common_str = strs[0];
for (int i=0; i<strs.size(); i++) {
if (minLen > strs[i].size()) {
minLen = strs[i].size();
common_str = strs[i];
}
}
for (int i=0; i<minLen; ++i) {
for (int j=0; j<strs.size(); ++j) {
if (common_str[i] != strs[j][i])
return common_str.substr(0, i);
}
if (i == minLen-1)
return common_str;
}
return "";
}
2. python版本
注:
python中min函数用法,不能传入空list!
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
common_str = min(strs, key=len)
min_len = len(common_str)
for i in range(min_len):
for j in range(len(strs)):
if common_str[i] != strs[j][i]:
return common_str[0:i]
if i == min_len-1:
return common_str
return ""
看了下提交python高赞版本,发现这个版本可以优化。
没必要判断i == min_len-1
,当初加这句是考虑['flow', 'fl', '12345', 'test']这种情况,其实 if common_str[i] != strs[j][i]: return common_str[0:i] 就可以返回""。
优化如下:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
common_str = min(strs, key=len)
min_len = len(common_str)
for i in range(min_len):
for j in range(len(strs)):
if common_str[i] != strs[j][i]:
return common_str[0:i]
return common_str
更加pythonic高赞版本 引用https://leetcode.com/problems/longest-common-prefix/discuss/6918/Short-Python-Solution
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
shortest = min(strs,key=len)
for i, ch in enumerate(shortest):
for other in strs:
if other[i] != ch:
return shortest[:i]
return shortest
网友评论