题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 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%的用户
