# 0014. Longest Common Prefix
###### tags: `Leetcode` `FaceBook` `Easy`
Link: https://leetcode.com/problems/longest-common-prefix/
## 思路
### 思路一 $O(max(M,N)*M)$ $O(1)$ N是字符串个数 M是字符串最大的长度
首先假设第一个是prefix，然后一点一点删掉
时间复杂度 第一个回圈跑N次 每次都要检查是否startsWith(prefix) 所以$O(M*N)$ 第二个while回圈一共最多跑M次，每次都要花$O(M)$ 所以第二个回圈的时间复杂度是$O(M^2)$ 分摊到N次回圈里
### 思路二 $O(N*M)$ $O(1)$
先找出最小的和最大的字符串，因为他们两个一定是差最多的，所以只要找出他们俩的prefix 就可以
## Code
### 思路一

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String prefix = strs[0];
        for(int i = 1;i < strs.length;i++){
            while(!strs[i].startsWith(prefix)){
                prefix = prefix.substring(0, prefix.length()-1);
            }
        }
        return prefix;
    }
}

### 思路二

class Solution {
    private int compare(String a, String b){
        return a.compareTo(b);
    }
    public String longestCommonPrefix(String[] strs) {
        String minStr = strs[0];
        String maxStr = strs[0];
        for(int i = 0;i < strs.length;i++){
            if(compare(minStr, strs[i])>=0) minStr = strs[i];
            if(compare(strs[i], maxStr)>=0) maxStr = strs[i];
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < Math.min(minStr.length(), maxStr.length());i++){
            if(minStr.charAt(i)==maxStr.charAt(i)) sb.append(minStr.charAt(i));
            else break;
        }
        return sb.toString();
    }
}