1.题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
2.题解
2.1方法一：横向扫描（做减法）
用 LCP(S1…Sn)表示字符串 S1…Sn 的最长公共前缀。
可以得到以下结论：
LCP(S1…Sn) = LCP(LCP(LCP(S1,S2),S3)，....Sn)
基于该结论，可以得到一种查找字符串数组中的最长公共前缀的简单方法。依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。
如果在尚未遍历完所有的字符串时，最长公共前缀已经是空串，则最长公共前缀一定是空串，因此不需要继续遍历剩下的字符串，直接返回空串即可。
代码
//
// Created by trmbh on 2023-10-14.
//
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) {
return ""; // 如果输入为空数组，直接返回空字符串
}
string prefix = strs[0]; // 以第一个字符串作为初始前缀
for (int i = 1; i < strs.size(); ++i) {
// 依次比较当前前缀和下一个字符串的公共前缀
int j = 0;
/* 1.长度小于当前最长前缀和待比较字符串，2.从头开始比较字符是否相等*/
while (j < prefix.size() && j < strs[i].size() && prefix[j] == strs[i][j]) {
++j;
}
// 做减法，更新前缀为公共前缀
prefix = prefix.substr(0, j);
// 如果当前前缀为空，说明没有公共前缀，可以直接返回
if (prefix.empty()) {
return "";
}
}
return prefix;
}
};
int main() {
vector<string> strs = {"flower", "flow", "flight"};
Solution solution;
string commonPrefix = solution.longestCommonPrefix(strs);
cout << "公共前缀: " << commonPrefix << endl;
return 0;
}
复杂度分析
时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)。使用的额外空间复杂度为常数。
2.2 纵向扫描（做加法）
方法一是横向扫描，依次遍历每个字符串，更新最长公共前缀。另一种方法是纵向扫描。纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
if (strs.empty()) return ""; // 如果输入为空数组，直接返回空字符串
for (int i = 0; i < strs[0].size(); i++)
for (int j = 1; j < strs.size(); j++)
if (strs[0][i] != strs[j][i]) return strs[0].substr(0, i);
return strs[0];
}
};
复杂度分析
时间复杂度：O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)。使用的额外空间复杂度为常数。
2.3方法三：分治（将大的问题分成两个小问题，使用递归的方式最终成为两两一组字符串）
注意到 LCP的计算满足结合律，有以下结论：
LCP(S1…Sn)=LCP(LCP(S1…Sk),LCP(Sk+1…Sn))
其中 LCP(S1…Sn) 是字符串S1...Sn的最长公共前缀，1 < k < n。
基于上述结论，可以使用分治法得到字符串数组中的最长公共前缀。对于问题 LCP(Si⋯Sj)，
可以分解成两个子问题 LCP(Si…Smid) 与 LCP(Smid+1…Sj)，
其中 mid=(i+j)/2 。对两个子问题分别求解，然后对两个子问题的解计算最长公共前缀，即为原问题的解。
//
// Created by trmbh on 2023-10-14.
// 14.公共前缀
#include <iostream>
#include <string>
#include <vector>
using namespace std;
/* 分治算法 */
class Solution {
public:
/* 主入口函数（相当于多米诺骨牌的第一推） */
string longestCommonPrefix(vector<string>& strs) {
if (!strs.size()) {
return "";
}
else {
return longestCommonPrefix(strs, 0, strs.size() - 1);
}
}
/* 递归，分治（每次将问题减半，最终化为两两一组的字符串比较问题，可以类比学过的树遍历中的递归（左子树，右子树）） */
string longestCommonPrefix(const vector<string>& strs, int start, int end) {
if (start == end) {
return strs[start];
}
else {
int mid = (start + end) / 2;
string lcpLeft = longestCommonPrefix(strs, start, mid);
string lcpRight = longestCommonPrefix(strs, mid + 1, end);
return commonPrefix(lcpLeft, lcpRight);
}
}
/* 处理两个字符串的最长公共前缀 */
string commonPrefix(const string& lcpLeft, const string& lcpRight) {
int minLength = min(lcpLeft.size(), lcpRight.size());
for (int i = 0; i < minLength; ++i) {
if (lcpLeft[i] != lcpRight[i]) {
return lcpLeft.substr(0, i);
}
}
return lcpLeft.substr(0, minLength);
}
};
int main() {
vector<string> strs = {"flower", "flow", "flight"};
Solution solution;
string commonPrefix = solution.longestCommonPrefix(strs);
cout << "公共前缀: " << commonPrefix << endl;
return 0;
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-common-prefix/solutions/288575/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度分析
时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
时间复杂度的递推式是 T(n)=2*T(n/2)+O(m)，通过计算可得 T(n)=O(mn)
空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
空间复杂度主要取决于递归调用的层数，层数最大为 log n，每层需要 m 的空间存储返回结果。
2.4 方法四：二分查找
显然，最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。
用 minLength 表示字符串数组中的最短字符串的长度，则可以在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。
每次取查找范围的中间值 mid，判断每个字符串的长度为 mid 的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于 mid，
如果不相同则最长公共前缀的长度一定小于 mid，通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。
代码
/* 二分查找法 */
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
if (strs.empty()) {
return "";
}
/* 找到最短字符串的长度 */
/* min_element 函数的返回值是指向数组中最小元素的迭代器，使用箭头操作符 -> 可以访问该元素的成员函数 size()*/
/*std::min一般用于求 a 与 b 的较小者 或者求 initializer_list ilist 中值的最小者。
std::min_element是求一个范围内的最小者的迭代器。范围可以是全部容器，也可以是容器的一个子区间。*/
int minLen = min_element(strs.begin(), strs.end(),
[](const string &s, const string &t) { return s.size() < t.size(); })->size();
// int minLen = INT_MAX;
// for (const string& str : strs) {
// minLen = min(minLen, static_cast<int>(str.length()));
// }
/* low和high表示最长前缀的范围，这里为了方便计算长度，所以直接用1了，表示第一个元素 */
int low = 1, high = minLen;
while (low <= high) {
int mid = (low + high) / 2;
/* 判断是否拥有长为mid的公共前缀 */
if (isCommonPrefix(strs, mid)) {
low = mid + 1; // 若是公共前缀，说明最长前缀最后一个字符位置肯定（大于等于）mid所在位置，向前推进
} else {
high = mid - 1; //若不是公共前缀，说明最长前缀最后一个字符位置（小于）mid所在位置，往回倒退
}
}
/* 最后low的位置正在最长公共前缀最后一个字符的后面一个）*/
/* （注意结束条件，high<low，每次其实是mid-high的范围，但我这里low=mid+1;所以其实是low-1-high的范围*/
/* 最后high < low的结束条件，恰恰是mid-high=mid的时候，即找到了最后一个字符*/
/* 一举两得，low既可以作为结束条件来限制，也可以将范围向后推进*/
return strs[0].substr(0, low - 1);
}
bool isCommonPrefix(vector<string> &strs, int len) {
string prefix = strs[0].substr(0, len);
for (int i = 1; i < strs.size(); ++i) {
if (strs[i].compare(0, len, prefix) != 0) {
return false;
}
}
return true;
}
};
复杂度分析
时间复杂度：O(mnlogm)，其中 m 是字符串数组中的字符串的最小长度，n 是字符串的数量。二分查找的迭代执行次数是 O(logm)，
每次迭代最多需要比较 mn 个字符，因此总时间复杂度是 O(mnlogm)。
空间复杂度：O(1)。使用的额外空间复杂度为常数。