longest-common-prefix

Longest Common Prefix – LeetCode 14

Problem

Description

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

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size() == 0) return string();
int tmp, result = strs[0].size(),width = result;
for(int i = 1; i != strs.size(); ++i){
tmp = (width <= result) ? width : result;
int j = 0;
for(;strs[0][j] == strs[i][j] && j != tmp; ++j) ;
if(result > j) result = j;
}
return strs[0].substr(0,result);
}
};

思路

要求最长前缀,采用的是从第一个字符串开始对其vector从头向尾进行横向遍历寻找最长前缀的方案。
最坏情况下,时间复杂度为$O(m \times n)$,$m$为字符串长度,$n$为字符串个数,空间复杂度是$O(1)$。
耗时$6$ ms,排名$70.16\%$。

Better

思路

这个思路来自LeetCode的官方Solution中的Vertical scanning。
最坏情况下,时间复杂度为$O(m \times n)$,$m$为字符串长度,$n$为字符串个数,空间复杂度是$O(1)$。但相较原方案将节省多余的横向遍历,带来更小的时间开销。
更多有趣思路在LeetCode官方解,虽然实际性能不如这个方案,但依旧值得一看。
耗时$6$ ms,排名$70.16\%$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size() == 0) return string();
for(int i = 0; i != strs[0].size(); ++i){
for(int j = 1; j != strs.size(); ++j){
if(i == strs[j].size()) return strs[0].substr(0,i);
if(strs[j][i] != strs[0][i]) return strs[0].substr(0,i);
}
}
return strs[0].substr(0,strs[0].size());
}
};