14. 最长公共前缀

本题来自 LeetCode：14. 最长公共前缀^[1]

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例  1:

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

示例  2:

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

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

暴力法

题目分析

本题可以依次比较 n个字符串的第 i个字符是否相同， i要小于这 n个字符串的最小长度。

题目解答

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null
            || strs.length == 0
            || strs[0] == null
            || strs[0].length() == 0) {
            return "";
        }
        int count = 0;
        for(int i = 0; i  strs[0].length(); i ++) {
            char c = strs[0].charAt(count);
            for(int j = 1; j  strs.length; j ++) {
                if(strs[j] == null
                    || strs[j].length() == count
                    || c != strs[j].charAt(count)) {
                    return strs[0].substring(0, count);
                }
            }
            count ++;
        }
        return strs[0].substring(0, count);
    }
}

复杂度分析：
时间复杂度： O(m * n)， m 为 n个字符串的最小长度。
空间复杂度： O(1)

分治法

题目分析

本题也可以采用分治法来解答，将数组拆分成两个子数组，分别对两个子数组求最长公共前缀，然后对得到这个两个公共前缀，再求公共前缀，就得到整个数组的最长公共前缀。

题目解答

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0) {
            return "";
        }
        return commonPrefix(strs, 0, strs.length - 1);
    }

    public String commonPrefix(String[] strs, int left, int right) {
        // 若只有一个字符串，直接返回
        if(left == right) {
            return strs[left];
        }
                // 中间位置
        int mid = left + (right - left) / 2;
        // [left, mid]的最长公共前缀
        String commonLeft = commonPrefix(strs, left, mid);
        // 防止越界
        if(mid + 1  right) {
            return commonLeft;
        }
        // [mid + 1, right]的最长公共前缀
        String commonRight = commonPrefix(strs, mid + 1, right);

        int length = Math.min(commonLeft.length(), commonRight.length());
        int i = 0;
        // 求commonLeft和commonRight的最长公共前缀
        while(i  length && commonLeft.charAt(i) == commonRight.charAt(i)) {
            i ++;
        }
        return commonLeft.substring(0, i);
    }
}

复杂度分析：
时间复杂度： O(m * n)， m 为 n个字符串的最小长度。
空间复杂度： O(m * log(n))

参考资料

14. 最长公共前缀: https://leetcode-cn.com/problems/longest-common-prefix/

原文始发于微信公众号（xiaogan的技术博客）：