LeetCode面试150——14最长公共前缀

题目难度：简单

默认优化目标：最小化平均时间复杂度。

Python默认为Python3。

1 题目描述

2 题目解析

3 算法原理及代码实现

3.1 横向扫描

3.2 纵向扫描

3.3 分治

3.4 二分查找

参考文献

1 题目描述

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

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

2 题目解析

输入一个字符串数组strs，输出strs中各单词的最长公共前缀。strs[i]表示第i个单词。暴力求解的方法是，选定strs[0]，然后和strs[1]比较，找到它们的最长公共前缀。然后和strs[2]比，找到它们的最长公共前缀，依次类推。设strs的长度为n，单词的长度为m，平均时间复杂度为O(mn)。

3 算法原理及代码实现

3.1 横向扫描

即暴力求解法。依次遍历每个数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串后，即可得到字符串数组中的最长公共前缀。

有一个特殊情况，如果最长公共字符串为空，直接返回即可，无需继续遍历。

平均时间复杂度为O(mn)，平均空间复杂度为O(1)。

C++代码实现

class Solution {
public:// 主函数：找到字符串数组中的最长公共前缀string longestCommonPrefix(vector<string>& strs) {// 如果字符串数组为空，返回空字符串if (strs.empty()) {return "";}
// 初始化最长公共前缀为第一个字符串string maxCommonPrefix = strs[0];int n = strs.size();
// 遍历字符串数组，从第二个字符串开始for (int i = 1; i < n; i++) {// 更新最长公共前缀maxCommonPrefix = longestCommonPrefix(maxCommonPrefix, strs[i]);// 如果最长公共前缀为空，提前退出循环if (maxCommonPrefix.empty()) {break;}}return maxCommonPrefix;}
// 辅助函数：找到两个字符串的最长公共前缀string longestCommonPrefix(const string& str1, const string& str2) {int n=min(str1.size(),str2.size());int index=0;
while(index<n && str1[index]==str2[index]){index++;}
return str1.substr(0,index);}
};

Python代码实现

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:n=len(strs)maxCommenPrefix=strs[0]
if not strs:return ""
for i in range(1,n):maxCommenPrefix=self.MCP(maxCommenPrefix,strs[i])if not maxCommenPrefix:break
return maxCommenPrefix
def MCP(self, str1, str2) -> str:n=min(len(str1),len(str2))index=0
while index<n and str1[index]==str2[index]:index+=1
return str1[:index]

3.2 纵向扫描

我们换个角度看strs，将每个单词纵向排列在一起，然后从前往后扫描每一列，直到每一列的字母不完全相同时停止。

平均时间复杂度为O(mn)，平均空间复杂度为O(1)。

C++代码实现

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {int n=strs.size();int m=strs[0].size();
if(!n){return "";}
for(int i=0;i<m;i++){char c=strs[0][i];for(int j=1;j<n;j++){if(i == strs[j].size() || c!=strs[j][i]){return strs[0].substr(0,i);}}}
return strs[0];
}
};

Python代码实现

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if not strs:return ""n = len(strs)m = len(strs[0])for i in range(m):c = strs[0][i]for j in range(1, n):if i == len(strs[j]) or strs[j][i] != c:return strs[0][:i]return strs[0]

3.3 分治

根据横向扫描，有如下数学公式

$LCP(S_1,\cdots,S_n)=LCP(LCP(S_1,\cdots,S_k),LCP(S_{k+1},\cdots,S_n))$

其中， $LCP(S_1,\cdots ,S_n)$ 是字符串 $S_1\cdots S_n$ 的最长公共前缀， $1<k<n$ 。

因此，我们可以取 $k=mid=\frac{i+j}{2}$ ，对于 $LCP(S_i,\cdots,S_j)$ 。

平均时间复杂度为O(mn)，平均空间复杂度为O(1)。

C++代码实现

class Solution {
public:// 主函数：找到字符串数组中的最长公共前缀string longestCommonPrefix(vector<string>& strs) {// 如果字符串数组为空，返回空字符串if (strs.empty()) {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);}
};

Python代码实现

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if not strs:return ""else:return self.longestCommonPrefixHelper(strs, 0, len(strs) - 1)
def longestCommonPrefixHelper(self, strs, start, end):if start == end:return strs[start]else:mid = (start + end) // 2lcpLeft = self.longestCommonPrefixHelper(strs, start, mid)lcpRight = self.longestCommonPrefixHelper(strs, mid + 1, end)return self.commonPrefix(lcpLeft, lcpRight)
def commonPrefix(self, lcpLeft, lcpRight):minLength = min(len(lcpLeft), len(lcpRight))for i in range(minLength):if lcpLeft[i] != lcpRight[i]:return lcpLeft[:i]return lcpLeft[:minLength]

3.4 二分查找

最长公共共前缀不会超过最短长度的单词，用minLength表示最短长度单词。在[0,minLength]之间使用二分查找。

平均时间复杂度为O(mn log m)，平均空间复杂度O(1)。

C++代码实现

class Solution {
public:// 函数用于找到字符串数组中的最长公共前缀string longestCommonPrefix(vector<string>& strs) {// 如果输入的字符串数组为空，返回空字符串if (!strs.size()) {return "";}// 找到数组中最短字符串的长度int minLength = min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size();int low = 0, high = minLength;// 使用二分查找法寻找最长公共前缀while (low < high) {int mid = (high - low + 1) / 2 + low;if (isCommonPrefix(strs, mid)) {low = mid;} else {high = mid - 1;}}// 返回最长公共前缀return strs[0].substr(0, low);}
// 辅助函数用于检查给定长度的前缀是否是所有字符串的公共前缀bool isCommonPrefix(const vector<string>& strs, int length) {string str0 = strs[0].substr(0, length);int n = strs.size();// 比较每个字符串的前缀与第一个字符串的前缀for (int i = 1; i < n; i++) {string str = strs[i];for (int j = 0; j < length; j++) {if (str0[j] != str[j]) {return false;}}}return true;}
};

Python代码实现

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if not strs:return ""minLength = min(len(s) for s in strs)low, high = 0, minLengthwhile low < high:mid = (high - low + 1) // 2 + lowif self.isCommonPrefix(strs, mid):low = midelse:high = mid - 1return strs[0][:low]
def isCommonPrefix(self, strs: List[str], length: int) -> bool:str0 = strs[0][:length]for i in range(1, len(strs)):if strs[i][:length] != str0:return Falsereturn True