LeetCode刷题实战14: 最长公共前缀-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做最长公共前缀 ，我们先来看题面：

https://leetcode-cn.com/problems/longest-common-prefix/

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

题意

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

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

样例

示例 1:

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

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

题解

解法一

这种解法是暴力循环法，从题目可知：最长公共前缀的最长长度一定是字符串数组中长度最短哪个字符串。

首先找出长度最短的字符串str，加入str="abcf"。
依次对'abcf'、'abc'、'ab'、'a'进行筛选，判断哪个是所有其他字符串的前缀。

public String longestCommontPrefix6(String[] strs) {
    if(strs.length == 0) {
        return "";
    }
    int min = Integer.MAX_VALUE;
    for(String str : strs) {
        min = Math.min(min, str.length());
    }
    int low = 1;
    int high = min;
    while(low <= high) {
        int middle = (low + high)/2;
        if(this.isCommontPrefix(strs, middle)) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    return strs[0].substring(0, (low + high)/2);
}

public boolean isCommontPrefix(String[] strs, int length) {
    String tmp = strs[0].substring(0, length);
    for (int i=0; i        if(!strs[i].startsWith(tmp)) {
            return false;
        }
    }
    return true;
}

解法二

这种方法称之为水平扫描法，用一张图来表示其具体过程如下：

首先假设最长前缀result=str[0], 遍历字符串数组，依次与result做比较，找出其最长前缀，然后更新result，再进行下一次比较。

public String longestCommonPrefix3(String[] strs) {
    if(strs.length == 0) {
        return "";
    }
    String result = strs[0];
    for(int i=0; i        while(strs[i].indexOf(result) != 0) {
            result = result.substring(0, result.length()-1);
            if(result.length() == 0) {
                return "";
            }
        }
    }
    return result;
}

解法三

利用二分法的思想

找出最短的字符串记为m;
对字符串m进行二分,分割点记为mid，用tmp表示m[low...high]。
如果tmp为所有字符串的前缀，则mid右移，否则左移，直到low>high。
代码如下：

public String longestCommontPrefix6(String[] strs) {
    if(strs.length == 0) {
        return "";
    }
    int min = Integer.MAX_VALUE;
    for(String str : strs) {
        min = Math.min(min, str.length());
    }
    int low = 1;
    int high = min;
    while(low <= high) {
        int middle = (low + high)/2;
        if(this.isCommontPrefix(strs, middle)) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    return strs[0].substring(0, (low + high)/2);
}

public boolean isCommontPrefix(String[] strs, int length) {
    String tmp = strs[0].substring(0, length);
    for (int i=0; i        if(!strs[i].startsWith(tmp)) {
            return false;
        }
    }
    return true;
}