【每日一题】LeetCode - 最长公共前缀
给定一个字符串数组 strs，寻找它们的最长公共前缀。如果不存在公共前缀，则返回空字符串 ""。
示例
示例 1
输入: strs = ["flower","flow","flight"]
输出: "fl"
示例 2
输入: strs = ["dog","racecar","car"]
输出: ""
解释：字符串数组中没有共同前缀，因此返回空字符串。
限制条件
- 数组长度
1 <= strs.length <= 200 - 字符串长度
0 <= strs[i].length <= 200 - 所有字符串均为小写英文字母
2. 解题思路与实现方法
方法 1：横向扫描法
将第一个字符串作为初始公共前缀，逐一与数组中的其他字符串对比，通过缩减前缀长度来保证公共性。最终得到的是所有字符串的最长公共前缀。
代码实现
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string prefix = strs[0]; // 初始前缀
for (int i = 1; i < strs.size(); ++i) {
int j = 0;
// 比较前缀与当前字符串的公共部分
while (j < prefix.size() && j < strs[i].size() && prefix[j] == strs[i][j]) {
++j;
}
prefix = prefix.substr(0, j); // 更新前缀长度
if (prefix.empty()) break; // 若前缀为空，直接返回
}
return prefix;
}
};
int main() {
Solution s;
vector<string> strs = {"flower", "flow", "flight"};
cout << s.longestCommonPrefix(strs) << endl;
return 0;
}
代码解析
- 初始设置：将
strs[0]作为初始公共前缀prefix。 - 逐个比较：遍历剩余的字符串，每次更新
prefix为其与当前字符串的公共前缀。 - 返回结果：当
prefix缩减为 0 时，立即返回空字符串；否则返回最终公共前缀。
时间复杂度计算
- 最坏情况：所有字符串长度相等且无公共前缀时，时间复杂度为
O(S)，其中S是数组中所有字符的总和。 - 平均情况：由于每次比较时前缀逐渐缩短，通常能达到
O(minLen * n)的效率，minLen为字符串中最小长度，n为字符串个数。
空间复杂度
仅使用常数额外空间，空间复杂度为 O(1)。
方法 2：动态规划
此问题可转化为动态规划问题，逐字符检查公共前缀的长度。
- 状态定义：定义
dp[i][j]表示到第i个字符串和第j个字符时的最长公共前缀长度。 - 状态转移方程：如果
strs[i][j] == strs[i-1][j]，则dp[i][j] = dp[i-1][j] + 1，否则dp[i][j] = 0。 - 初始条件：第一个字符串为初始公共前缀，依次向后遍历更新。
代码实现
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
int n = strs.size();
int minLen = INT_MAX;
// 寻找最小字符串长度
for (const string& s : strs) {
minLen = min(minLen, (int)s.length());
}
int low = 1, high = minLen;
while (low <= high) {
int mid = (low + high) / 2;
if (isCommonPrefix(strs, mid))
low = mid + 1;
else
high = mid - 1;
}
return strs[0].substr(0, (low + high) / 2);
}
private:
bool isCommonPrefix(const vector<string>& strs, int len) {
string prefix = strs[0].substr(0, len);
for (int i = 1; i < strs.size(); i++) {
if (strs[i].find(prefix) != 0) {
return false;
}
}
return true;
}
};
int main() {
Solution solution;
vector<string> strs = {"flower", "flow", "flight"};
cout << solution.longestCommonPrefix(strs) << endl;
return 0;
}
代码解析
- 初始化：找到最短字符串的长度，设为
minLen。 - 二分搜索：通过二分法逐步缩小范围，判断当前长度是否是公共前缀。
- 判断公共前缀：利用
isCommonPrefix函数检查当前长度len是否为公共前缀。 - 返回结果：最终获得的
(low + high) / 2即最长公共前缀长度。
时间复杂度分析
- 二分查找的复杂度为
O(log minLen)，每次查找调用isCommonPrefix的时间复杂度为O(n * minLen)。因此总复杂度为O(n * minLen * log minLen)。 - 空间复杂度为
O(1)。
方法 3：纵向扫描法
逐列检查每个字符是否相同，遇到不同则停止。这种方法直观易懂，适用于小规模字符串数组。
代码实现
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
for (int i = 0; i < strs[0].size(); i++) {
char c = strs[0][i];
for (int j = 1; j < strs.size(); j++) {
if (i == strs[j].size() || strs[j][i] != c) {
return strs[0].substr(0, i);
}
}
}
return strs[0];
}
3. 方法对比与总结
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 横向扫描法 | O(S) | O(1) | 字符串较多 |
| 二分法+动态规划 | O(n * minLen * log minLen) | O(1) | 大规模字符串 |
| 纵向扫描法 | O(S) | O(1) | 小规模字符串 |
- 横向扫描法和纵向扫描法都适合中小规模数据，横向法代码更简洁。
- 二分法结合动态规划提升了效率，适用于需要更高效率的情况。
原文地址：https://blog.csdn.net/qq_37945670/article/details/143448869
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！