最长公共前缀贪心法
时间: 2023-07-04 11:14:26 浏览: 62
最长公共前缀可以使用贪心法来解决。假设我们有一个字符串数组,我们可以先找到这些字符串中长度最短的那个字符串,然后从这个字符串的第一个字符开始,依次比较每个字符串的相应位置的字符是否相同,如果相同,则继续比较下一个字符,如果不同,则停止比较,返回当前的最长公共前缀。
具体算法实现如下:
1. 找到字符串数组中长度最短的字符串,假设长度为minLen
2. 从第一个字符开始,依次比较每个字符串的相应位置的字符是否相同,直到遇到不同的字符或者到达minLen位置
3. 返回当前的最长公共前缀
代码示例:
```
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
int minLen = INT_MAX;
for (string str : strs) {
minLen = min(minLen, (int)str.size());
}
for (int i = 0; i < minLen; i++) {
char c = strs[0][i];
for (int j = 1; j < strs.size(); j++) {
if (strs[j][i] != c) {
return strs[0].substr(0, i);
}
}
}
return strs[0].substr(0, minLen);
}
};
```
注意:该算法的时间复杂度为O(n * m),其中n是字符串数组的长度,m是字符串的平均长度。