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());
}
};
|