编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
提示：
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题相对简单，有几个思路：
从头到位，每一个字符判断
这个是最简单也最容易想到的，就是从第一个字符开始，判断每一个字符串的第一个字符是否一样，如果一样，就继续下一个，如果不一样，就结束，如果有的字符串已经到最后一位，也结束。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string sret;
int i = 0;
char p = 0;
bool bret = true;
if(strs.empty())
{
bret = false;
}
while(bret)
{
p = 0;
for(auto& iter : strs)
{
if(iter.size() <= i)
{
bret = false;
break;
}
else if(p == 0)
{
p = iter[i];
}
else if(p != iter[i])
{
bret = false;
break;
}
}
i++;
if(bret)
{
sret = sret + p;
}
}
return sret;
}
};
每个字符串单独判断
这个就是从头到尾，每个字符串与得到的前面的公共前缀比较，第一组就是前两个比较，得到公共前缀，然后用公共前缀和第三个比较，以此类推。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string sret;
bool bfirst = true;
for(auto& iter : strs)
{
if(bfirst)
{
bfirst = false;
sret = iter;
continue;
}
int len = sret.size();
if(len > iter.size())
{
len = iter.size();
}
if(len > 0)
{
sret = sret.substr(0, len);
for(int i = 0; i < len; i++)
{
if(sret[i] != iter[i])
{
sret = sret.substr(0, i);
break;
}
}
}
else
{
sret = "";
}
if(sret.empty())
{
break;
}
}
return sret;
}
};
二分法
这种方法就是把字符串数组按照二分法，然后每一半单独查找公共前缀，最后再对比两遍的结果。
另一种二分法
这种二分法是先找到最小长度的字符串，比如是n，然后按照二分法，先查找n/2的位置是否是公共前缀，如果是，就再找后面的，如果不是就再找前面的。