leetcode题记 14.最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 “”。

示例 1:

输入: [“flower”,”flow”,”flight”]
输出: “fl”

示例 2:

输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

来源:力扣(LeetCode)

题解

这道题从官方题解上来看,无论是何种办法时间复杂度均为O(S)【S为字符串合集中的字符个数】。许多需要预处理的办法中虽然查找的过程时间复杂度为O(log n),但是预处理需要的时间也是O(S),并且空间复杂度也会从S(n)上升到S(S),所以这道题我觉得最好的结题思路就是暴力遍历法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
string getCommonPrefix(string a, string b) {
int n = min(a.length(), b.length());
string res = "";
for (int i = 0; i < n; i++) {
if (a[i] == b[i]) {
res += a[i];
} else {
break;
}
}
return res;
}
string longestCommonPrefix(vector<string>& strs) {
int n = strs.size();
if (n == 0) {
return string("");
} else if (n == 1) {
return strs[0];
}
string res = strs[0];
for (int i = 1; i < n; i++) {
res = getCommonPrefix(res, strs[i]);
}
return res;
}
};

结果

执行用时 : 4 ms, 在所有 C++ 提交中击败了97.34%的用户
内存消耗 : 9.3 MB, 在所有 C++ 提交中击败了66.19%的用户

加上

1
2
3
4
5
static auto x = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
return 0;
}();

之后:

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 : 9.4 MB, 在所有 C++ 提交中击败了51.25%的用户

Author: SmallXeon
Link: https://hexo.chensmallx.top/2019/07/25/leetcode-14-longestCommonPrefix/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
一些推广链接
几个便宜量大的小✈场: FASTLINK, YToo, 论坛邀请注册: ,
便宜量大但是稳定性不足的VPS: , 价格略贵但好用的VPN: , ,