LeetCode-Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix

最长前缀匹配问题，最直观的思路的程序如下：

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        prefix=''
        if len(strs)>0:
            minLen=min(map(lambda x:len(x),strs))
            for i in range(minLen):
                s=strs[0][i]
                addFlag=True
                for str in strs:
                    if str[i]!=s:
                        addFlag=False
                        break
                if addFlag:
                    prefix=prefix+s
                else:
                    break
        return prefix

用时 39ms

使用 Java，不进行字符串的不断截取，只进行前缀长度的记录，并且将边界情况直接用 if 进行排除。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0){
            return "";
        }else if(strs.length==1){
            return strs[0];
        }
        int prefix_len=strs[0].length();
        for(int i=1;i<strs.length;i++){
            if(strs[i].length()<prefix_len){
                prefix_len=strs[i].length();
            }
            for(int j=0;j<prefix_len;j++){
                if((strs[i].charAt(j)!=strs[0].charAt(j))){
                    prefix_len=j;
                    break;
                }
            }
            if(prefix_len==0){
                return "";
            }
        }
        return strs[0].substring(0,prefix_len);
    }
}

用时少于 85.96%的人。

看了一下官方的标准答案，除了我这里 Python 和 Java 代码中所用的思想以外，还有二分查找、分治和建树的思想，其中二分查找有将字符串集合二分和将单个字符串进行二分，这些思想非常重要。

使用二分法进行查找的方法如下：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size()==0) return "";
        else if(strs.size()==1) return strs[0];
        int len = helper(strs);
        return strs[0].substr(0,len);
    }
    
    int helper(vector<string>& strs) {
        int mid = strs.size()/2;
        return getCommonPrefix(strs[0], helper(strs, 0, mid), strs[mid], helper(strs, mid, strs.size()));
    }
    
    int helper(vector<string>& strs, int left, int right) {
        if(right-left == 1) return strs[left].size();
        else if (right-left == 2) return getCommonPrefix(strs[left], strs[left].size(), strs[left+1], strs[left+1].size());
        int mid = (left+right)/2;
        return getCommonPrefix(strs[left], helper(strs, left, mid), strs[mid], helper(strs, mid, right));
    }
    
    int getCommonPrefix(string& s1, int len1, string& s2, int len2) {
        int maxLen = min(len1, len2);
        int commonLen = 0;
        for(int i=0; i<maxLen; ++i) {
            if(s1[i]==s2[i]) commonLen++;
            else break;
        }
        return commonLen;
    }
};