[数据结构与算法]leetcode14-最长公共前缀

一.题目描述

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

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

示例 1：

输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
示例 2：

输入：strs = [“dog”,“racecar”,“car”]
输出：""
解释：输入不存在公共前缀。

提示：

0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

二.题目解析

1.暴力法

public static String longestCommonPrefix(String[] strs) {
        /*前两个字符串找公共子串，将其结果和第三个字符串找公共子串……直到最后一个串
        时间性能为O(n*m)
        * */
        if(strs == null || strs.length == 0){
            return null;
        }
        //当只有一个字符串时，最长公共前缀为自身
        if(strs.length == 1){
            return strs[0];
        }
        //最长公共前缀用[0,finalLast]记录
        int pointer = 0,max = Integer.MAX_VALUE,finalLast = 0;
        for (int i = 0,j = i + 1; i < strs.length - 1 && j < strs.length; i++,j++) {
            String before = strs[i];
            String after = strs[j];
            while ((pointer < before.length()) && (pointer < after.length()) && (before.charAt(pointer) == after.charAt(pointer))){
                pointer++;
            }
            //如果交集部分长度变小，那么最长公共前缀必定也缩小
            if(pointer < max){
                max = pointer;
                finalLast = pointer - 1;
            }
            //下轮比较中更新pointer为0
            pointer = 0;
        }

        return strs[0].substring(0, finalLast + 1);

    }

2.

public String longestCommonPrefix2(String[] strs) {
        /*先排序，然后比较最大和最小的字符串的公共前缀即可
        时间复杂度：O(nlogn + m)
        * */
        if(strs == null || strs.length == 0){
            return null;
        }
        Arrays.sort(strs);
        String min = strs[0];
        String max = strs[strs.length - 1];
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < min.length() && i < max.length(); i++) {
            if(min.charAt(i) == max.charAt(i)){
                builder.append(min.charAt(i));
            }else{
                break;
            }
        }
        return builder.toString();
    }

3.

public String longestCommonPrefix1(String[] strs) {
        if(strs.length==0)return "";
        //公共前缀比所有字符串都短，随便选一个先
        String s=strs[0];
        for (String string : strs) {
            while(!string.startsWith(s)){
                if(s.length()==0)return "";
                //公共前缀不匹配就让它变短！
                s=s.substring(0,s.length()-1);
            }
        }
        return s;
    }