leetcode--14--最长公共前缀

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

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

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

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

说明:

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

链接：https://leetcode-cn.com/problems/longest-common-prefix

思路：
1、依次同时遍历数组中的字符串，如果字符串前缀一样则继续遍历，否则返回上一轮前缀的结果

Python代码：

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        ret = ""
        for i in range(len(strs[0])):
            pref = strs[0][:i+1]
            for str in strs:
                if str[:i+1] != pref:
                    return ret
            ret = pref
        return ret

C++代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size()==0) return "";

        string ret="";
        for (int i=0; i<strs[0].size(); i++){
            string pref = strs[0].substr(0,i+1);
            for (string str : strs){
                if (str.substr(0,i+1)!=pref) return ret;
            }
            ret = pref;
        }
        return ret;
    }
};

思路2：
1、找到strs中最大、最小的两个字符串，比较这两个字符串的最长公共前缀即可

Python代码：

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        mmin = min(strs)
        mmax = max(strs)

        ret = ""
        for i,item in enumerate(mmin):
            if item!=mmax[i]:
                return ret
            ret = mmin[:i+1]
        return ret

C++代码：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size()==0) return "";

        string mmin = *max_element(strs.begin(), strs.end());
        string mmax = *min_element(strs.begin(), strs.end());

        string ret = "";
        for (int i=0; i<mmin.size(); i++){
            if (mmin[i]!=mmax[i]) return ret;
            ret = mmin.substr(0,i+1);
        }
        return ret;
    }
};