LC_最长公共前缀

发表于 分类于 ， 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

LC最长公共前缀

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

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

示例1:

输入：["flower","flow","flight"]

输出：[fl]

示例2:

输入：["dog","racecar","car"]

输出：""

解释：输入不存在公共前缀

说明：

所有人输入只包含小写字母a-z。

思路1：

1，当字符串数组长度为0时，则公共前缀为空，直接返回
2，令最长公共前缀ans的值为第一个字符串，进行初始化
3，遍历后面的字符串，依次将其与res进行比较，两两找出公共前缀，最终结果即为最长公共前缀
4，如果查找过程中出现了res为空的情况，则公共前缀不存在，直接返回
时间复杂度为O(s),s为所有字符串的长度之和

比如示例1；

res = flower

​ flow

res = flow

​ flight

res = fl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
    	if(strs.size() == 0) return "";
    	string res = strs[0];
    	int minlen = res.size();//记录公共前缀
    	for(int i = 1; i < strs.size(); i++){
    		int j = 0;
    		for(; j < res.size() && j < strs[i].size(); j++){
    			if(res[j] != strs[i][j]) break;
    		}
    		if(j <= minlen){
    			res = string(res,0,j);
    			minlen = j;
    		}
    		if(res.empty()) return res;
    	}
    	return res;
    }
};
思路2:

思路1:
1，我们先对字符串排序
比如abc ab abce
排序完后为
ab abc abce

2，比较头尾即可

复杂度为sort的复杂度

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
    	if(strs.empty()) return string();
    	sort(strs.begin(), strs.end());
    	string st = strs.front(), end = strs.back();
    	int i, num = min(st.size(),end.size());
    	for(i = 0; i < num && st[i] == end[i]; i++);
    	return string(st,0,i);
    }
};