14. 最长公共前缀

题目

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

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

示例 1：

示例 2：

提示：

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

解答（C++）

方法一【暴力】

假设strs=【a,b,c,d,e】

我们可以先求字符串a、b的最长公共前缀 为temp

temp再与c求...

...

简言之

就是每次求两个字符串的最长公共前缀 结果再和后面一个字符串求...

class Solution {
public:
    // 寻找字符串a、b的最长公共前缀
    string twoStrOfCommonPrefix(string a,string b){
        int index=0;
        while(a[index]==b[index] && index<a.length() && index<b.length()){
            ++index;
        }
        return a.substr(0,index);
    }
    string longestCommonPrefix(vector<string>& strs) {
        int n=strs.size();
        if(n==0) return "";
        string firstStr=strs[0];
        for(int i=1;i<n;++i){
            firstStr=twoStrOfCommonPrefix(firstStr,strs[i]);
            if(firstStr.size()==0) break;
        }
        return firstStr;
    }
};

方法一【】

class Solution
{
public:
	string longestCommonPrefix(const string &str1, const string &str2)
	{
		int length = min(str1.size(), str2.size());
		int index = 0;
		while (index < length && str1[index] == str2[index])
		{
			++index;
		}
		return str1.substr(0, index);
	}
	string longestCommonPrefix(vector<string> &strs)
	{
		if (!strs.size())
		{
			return "";
		}
		string prefix = strs[0];
		int count = strs.size();
		for (int i = 1; i < count; ++i)
		{
			prefix = longestCommonPrefix(prefix, strs[i]);
			if (!prefix.size())
			{
				break;
			}
		}
		return prefix;
	}
};