题目

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

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

示例1

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

示例2

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

说明

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

思路

暴力解法

首先使用for循环让数组遍历。在这个循环中，让每个字符串里面的字符一一对比，直到对比到不相同的字符就退出。然后在这个不同的位置上切割，把前面相同的部分取出来。把取出来的这部分拿到跟下一个字符串对比。

例如：["lexinhu","lexinw","lexi"]

让前两个字符串中两个字符一一对比（可以用到while循环），到h和w这两个不同的位置时跳出循环，截取lexin，让lexin与lexi对比，截取到lexi，返回lexi即可。

Java自带的方法

针对上面的思路，我们可以用Java-String中的startWith()方法，判断第二个字符串是否以第一个字符串开头，如果不是，让第一个字符串裁剪掉一个尾部字符，继续对比。

例如：["lexinhu","lexinw","lexi"]

使用lexinhu与lexinw对比，不同时，lexinhu裁剪掉u，剩下lexinh，继续对比，直到lexin，刚好lexinw是以这个开头的，此时这个公共部门就是lexin，跟第三个字符lexi对比，执行相同的操作。

代码实现

暴力解

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String s = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int index = 0;
            while (
                    index < (Math.min(s.length(),strs[i].length()))
                    && s.charAt(index) == strs[i].charAt(index)
            ){
                index++; 
            }
            s = strs[i].substring(0, index);
            if(s.length() == 0){
                return s;
            }
        }
        return s;
    }
}

优化后

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