【算法】LeetCode算法题-Longest Common Prefix

来源：cnblogs　　作者：小川94　　时间：2018/10/20 15:13:01　　对本文有异议

这是悦乐书的第146次更新，第148篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第5题（顺位题号是14），给定一个随机的字符串数组，查找这些字符串元素的公共前缀字符串，如果没有则返回空串。其中，字符串数组中的元素都是由小写字母a-z之间随机组合而成。例如：

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

输入: ["dog","racecar","car"]
输出: ""

输入：["c"]
输出："c"

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

第一步：获取数组的第一个元素first。

第二步：截取first字符串的0-1位，判断数组从第二个元素到最后一个元素是否都能匹配到截取的字符串，匹配到count就加1，如果count最后的值和数组除掉第一个元素后的长度相等，则是共有前缀。

第三步：如果第二步成功匹配上，则截取first字符串的0-2位，重复第二步的判断逻辑。

public static String longestCommonPrefix(String[] strs) {
    String result = "";
    if (strs.length == 0) {
        return "";
    }
    if (strs.length == 1) {
        return strs[0];
    }
    String first = strs[0];
    for (int i=1; i<=first.length(); i++) {
        String prefix = first.substring(0, i);
        int count = 0;
        for (int j=1; j<strs.length; j++) {
            if (strs[j].indexOf(prefix) == 0) {
                count = count + 1 ;
            }
        }
        if (count != 0 && count == strs.length-1) {
            result = prefix;
        }
    }
    return result;
}

03 第二种解法

第一步：获取数组中第一个元素first。

第二步：用first和数组第二个元素匹配查找，找不到就循环将first元素从0到倒数第二位截取，直到first变为空，如果first为空则表示没有相同的前缀。

第三步：用first和数组第二个元素的共有前缀与数组第三个元素进行匹配查找，依次往后循环。

public static String longestCommonPrefix2(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    String first = strs[0];
    for (int i=1; i<strs.length; i++) {
        while (strs[i].indexOf(first) != 0) {
            first = first.substring(0, first.length()-1);
            if (first.isEmpty()) {
                return "";
            }
        }
    }
    return first;
}

04 第三种解法

先将原数组分为两部分，左边部分依次获取共有前缀，右边部分依次获取共有前缀，再将左右两边的前缀进行查找，最后得到所有元素共有的前缀。此方法有点绕，可以通过调试或做标记及的方式理解。

public String longestCommonPrefix3(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    return partOf(strs, 0, strs.length-1);
}
public String partOf(String[] strs, int leftIndex, int rightIndex) {
    if (leftIndex == rightIndex) {
        return strs[leftIndex];
    } else {
        int midIndex = (leftIndex + rightIndex)/2;
        String leftStr = partOf(strs, leftIndex, midIndex);
        String rightStr = partOf(strs, midIndex+1, rightIndex);
        return getResult(leftStr, rightStr);
    }
}
public String getResult (String leftStr, String rightStr) {
    int min = Math.min(leftStr.length(), rightStr.length());
    for (int i=0; i<min; i++) {
        if (leftStr.charAt(i) != rightStr.charAt(i)) {
            return leftStr.substring(0, i);
        }
    }
    return leftStr.substring(0, min);
}