leetcode题解:最长公共前缀

题目描述

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

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

示例 1:

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

示例 2:

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

说明:

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

思路与代码

//1,计算最短的字符串的长度
        //2，挨个比较每个字符串的前minLength位
            //2.1 while循环，求得公共字符
        String res ="";
        int minLength = Integer.MAX_VALUE;
        if (strs.length == 0){
            return res;
//            System.out.println("res========"+res);
        }else{
            for (int i = 0; i < strs.length; i++) {
                minLength = Math.min(minLength, strs[i].length());
            }
            int index = 0 ; //起始位
            loop:
            while (index < minLength){
                String current = "";
                for (int i = 0; i < strs.length; i++) {
                    String ch = strs[i].charAt(index)+"";
                    if( i == 0 ){
                        current = ch ;
                    }else {
                        if (!current.equals(ch)){
                            current ="";
                            break loop;
                        }
                    }
                }
                res += current;
                index++;
            }
            return res;
//            System.out.println("结果是======"+res);
        }

结果分析

官方显示，此种算法最low，因为双重循环，时间复杂度是O（n²），那么有没有什么更好的解决办法呢？

二分查找法

思路

先取得最短字符串的长度，然后进行二分比较，首先，把该长度切一半，如果这一半都一样，那么再剩余的一半字符串中再取一半，反之，如果前一半不一样，则比较前一半的前一半的字符串，依次进行

代码

public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        int low = 0, high = minLength;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (isCommonPrefix(strs, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return strs[0].substring(0, low);
    }
public boolean isCommonPrefix(String[] strs, int length) {
    String str0 = strs[0].substring(0, length);
    int count = strs.length;
    for (int i = 1; i < count; i++) {
        String str = strs[i];
        for (int j = 0; j < length; j++) {
            if (str0.charAt(j) != str.charAt(j)) {
                return false;
            }
        }
    }
    return true;
}

分析

时间复杂度：O(mn log m)O(mnlogm)，其中 mm 是字符串数组中的字符串的最小长度，nn 是字符串的数量。二分查找的迭代执行次数是 O(\log m)O(logm)，每次迭代最多需要比较 mnmn 个字符，因此总时间复杂度是 O(mn \log m)O(mnlogm)。

空间复杂度：O(1)O(1)。使用的额外空间复杂度为常数。