Write a function to find the longest common prefix string amongst an array of strings.

1. 解法一

思路

对字符串数组进行排序，比较第一个字符串和最后一个字符串的公共前缀

代码

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        strs.sort()
        for i in range(min(len(strs[0]), len(strs[-1]))):
            if strs[0][i] != strs[-1][i]:
                return strs[0][0:i]
        return strs[0]      

解法二

思路

从长度入手，利用二分法不断寻找最大的公共前缀的长度。

public class Solution{
  public String longestCommonPrefix(String[] strs){
    if(strs == null || strs.length == 0){
      return "";
    }
    int minLen = Integer.MAX_VALUE;
    for (String str:strs) {
      minLen = Math.min(minLen, str.length());
    }
    int low = 0;
    int high = minLen;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (isPrefix(strs, mid)) {
        low = mid + 1;
      }else{
        high = mid - 1;
      }
    }
    return strs[0].substring(0, (low+high)/2);
  }
  private boolean isPrefix(String[] strs, int len){
    String str1 = strs[0].substring(0, len);
    for(int i= 1; i < strs.length; i++){
      if(!strs[i].startsWith(str1)){
        return false;
      }
    }
    return true; 
  }
}