【每日一题】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>usingnamespace std;classSolution{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;}};intmain(){ Solution s; vector<string> strs ={"flower","flow","flight"}; cout << s.longestCommonPrefix(strs)<< endl;return0;}

代码解析

1. 初始设置：将 strs[0] 作为初始公共前缀 prefix。
2. 逐个比较：遍历剩余的字符串，每次更新 prefix 为其与当前字符串的公共前缀。
3. 返回结果：当 prefix 缩减为 0 时，立即返回空字符串；否则返回最终公共前缀。

时间复杂度计算

• 最坏情况：所有字符串长度相等且无公共前缀时，时间复杂度为 O(S)，其中 S 是数组中所有字符的总和。
• 平均情况：由于每次比较时前缀逐渐缩短，通常能达到 O(minLen * n) 的效率，minLen 为字符串中最小长度，n 为字符串个数。

空间复杂度

仅使用常数额外空间，空间复杂度为 O(1)。

方法 2：动态规划

此问题可转化为动态规划问题，逐字符检查公共前缀的长度。

1. 状态定义：定义 dp[i][j] 表示到第 i 个字符串和第 j 个字符时的最长公共前缀长度。
2. 状态转移方程：如果 strs[i][j] == strs[i-1][j]，则 dp[i][j] = dp[i-1][j] + 1，否则 dp[i][j] = 0。
3. 初始条件：第一个字符串为初始公共前缀，依次向后遍历更新。

代码实现

#include<iostream>#include<vector>#include<string>usingnamespace std;classSolution{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:boolisCommonPrefix(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){returnfalse;}}returntrue;}};intmain(){ Solution solution; vector<string> strs ={"flower","flow","flight"}; cout << solution.longestCommonPrefix(strs)<< endl;return0;}

代码解析

1. 初始化：找到最短字符串的长度，设为 minLen。
2. 二分搜索：通过二分法逐步缩小范围，判断当前长度是否是公共前缀。
3. 判断公共前缀：利用 isCommonPrefix 函数检查当前长度 len 是否为公共前缀。
4. 返回结果：最终获得的 (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. 方法对比与总结

• 横向扫描法和纵向扫描法都适合中小规模数据，横向法代码更简洁。
• 二分法结合动态规划提升了效率，适用于需要更高效率的情况。