本文共 3446 字，大约阅读时间需要 11 分钟。

14.最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。（所有输入只包含小写字母 a-z ）

官方题解

水平扫描

解题思路：将第一个字符串作为暂时的公共前缀，往后遍历，逐渐得到所有字符串的公共前缀。

public static String longestCommonPrefix00(String[] strs){    if(strs==null||strs.length==0) return "";//传进空数组    //将第一个字符串作为暂时作为公共前缀    String prefix = strs[0];    for (int i = 1; i < strs.length ; i++) {        while(strs[i].indexOf(prefix)!=0){//不等于0说明第一个字符串并不是该字符串的前缀，则向前推移            //prefix.substring(0,prefix.length()-1)  除去该字符串的最后一个字符            prefix = prefix.substring(0,prefix.length()-1);            //取到第一个字符，还是没有公共前缀，返回“”            if(prefix.isEmpty()) return "";        }    }    return prefix;}

复杂度分析

• 时间复杂度：O(S)，S 是所有字符串中字符数量的总和。

  最坏的情况下，n 个字符串都是相同的。算法会将 S1 与其他字符串都做一次比较。这样就会进行 S 次字符比较，其中 S 是输入数据中所有字符数量。

• 空间复杂度：O(1)，我们只需要使用常数级别的额外空间。

垂直扫描

解题思路：

public static String longestCommonPrefix01(String[] strs){    if(strs==null||strs.length==0) return "";    //该for循环表示从前往后遍历比较某一个字符串每个位上的字符    for(int i = 0;i

复杂度分析：

• 时间复杂度：o(s),s是所有字符串的总字符数。
  最坏的情况，输入n个长度为m的相字符串，s=nm。最坏的情况和第一种一样，但是最好的情况下，只需要进行[字符串个数][最短字符串的长度]次数的比较。
• 空间复杂度：o(1)，只需要常数级别的额外空间。

分治解法

解题思路：即将所有字符串拆分，每一部分的公共前缀的公共前缀，必然是所有字符串的公共前缀。

public static String longestCommonPrefix02(String[] strs){        if(strs == null||strs.length==0) return "";        return longestCommonPrefix(strs,0,strs.length-1);    }    private static String longestCommonPrefix(String[] strs,int left,int right){        //跳出递归的情况        if(left==right){            return strs[left];        }        else{            //分治            int mid = (left+right)/2;            String lcpLeft = longestCommonPrefix(strs,left,mid);            String lcpRight = longestCommonPrefix(strs,mid+1,right);            return CommonPrefix(lcpLeft,lcpRight);        }    }    //普通比较两个字符串的最长前缀的方法，按字符比较，最多是到其中较短的字符串的长度位数位置    private static String CommonPrefix(String left,String right){        //min变量存储较短字符串的长度        int min = Math.min(left.length(),right.length());        for (int i = 0; i < min; i++) {            //两边字符串对应字符比较，一旦不一样，就截取到之前一位            if(left.charAt(i)!=right.charAt(i)) return left.substring(0,i);        }        //跳出for循环，说明较短的字符串就是公共前缀        return left.substring(0,min);    }

复杂度分析：

• 时间复杂度：o(s),s是所有字符串的总字符数。
  最坏的情况，输入n个长度为m的相字符串。但是最好的情况下，只需要进行[字符串个数]*[最短字符串的长度]次数的比较。
• 空间复杂度：o(mlog(n))
  内存开支主要是递归过程中使用栈空间所消耗。log(n)次递归，每次需要m的空间存储返回结果。

二分查找

解题思路：最短字符串的长度就是公共前缀的最大可能长度。将字符串一分为二，每次经过判断，丢弃一部分，最终找到公共前缀。

public static String longestCommonPrefix03(String[] strs){    if(strs==null||strs.length==0) return "";    int minLen = Integer.MAX_VALUE;    //最长公共前缀的最大可能长度就是最短的字符串长度    //找出字符串数组中最短字符串的长度  minLen    for(String str:strs)        minLen = Math.min(minLen,str.length());    int low = 1;    int high = minLen;    while(low<=high){        //将查找空间一分为二        int mid =(low+high)/2;        //如果第一个字符串前面一半字符是所有串的公共前缀，那么就可以丢弃前一半查找空间        if(isCommonPrefix(strs,mid))            low = mid +1;        //如果不是的话，丢弃后一半        else            high = mid -1;    }    //找到最长前缀的最后位置，并返回    return strs[0].substring(0,(low+high)/2);}//判断传入数组的第一个字符串的前len位是不是后面的前缀，是返回true， 不是返回falseprivate static boolean isCommonPrefix(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;}

复杂度分析：

• 时间复杂度：o(s·log(n)),s是所有字符串的总字符数。
  最坏的情况，输入n个长度为m的相字符串。一共进行log(n)次迭代，每次都会进行s次比较。
• 空间复杂度：o(1)，只需要常数级别的额外空间。