LeetCode --- 14.最长公共前缀

LeetCode --- 字符串、数组
简书专栏：https://www.jianshu.com/nb/41796568
知乎专栏：https://zhuanlan.zhihu.com/c_174823416

一、题目描述

来源：力扣（LeetCode）
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

输入: ["flower","flow","flight"]
输出: "fl"
输入: ["dog","racecar","car"]
输出: ""
说明:
所有输入只包含小写字母 a-z 。

要求实现函数：
public String longestCommonPrefix(String[] strs) {}

二、实现思路以及代码

2.1 思路一：暴力破解法

先找出字符串数组中最短的字符串，记录其长度为min，以第一个字符串为基准，遍历长度为min,依次和字符串数组中的其他字符串相比较，如果都一样，则遍历下一位，一直到出现不同的字符为止，结束循环。

2.1.1 暴力破解实现代码

public static String longestCommonPrefix1(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        StringBuffer br = new StringBuffer();

        //最短数组长度
        int min = strs[0].length();
        for(int i = 1; i < strs.length; i++) {
            if (min > strs[i].length()) {
                min = strs[i].length();
            }
        }

        //匹配最短前缀
        for(int j = 0; j< min; j++) {
            char c = strs[0].charAt(j);
            for(int k = 1; k < strs.length; k++) {
                if(c != strs[k].charAt(j)){
                    return br.toString();
                }
            }
            br.append(c);
        }
        return br.toString();
    }

2.2 思路二：字符串巧解 水平扫描法

利用String类自带的函数indexOf()来进行数据处理，indexOf()函数返回的是目标字符串在当前字符串中所在的位置，如果当前字符串不存在目标字符串则返回-1。本算法实现思路是依次扫描字符串数组，以第一个字符串prefix为基准，如果后续字符串中prefix的位置不是在其初始位置，那么就对prefix进行从后向前缩减一个字符。可以理解为，prefix字符串和当前字符串取其从首字母开始的最长公共前缀，然后再求与下一个字符串的公共前缀，直到字符串数组遍历完成。其中，若prefix减为”“了，则表明没有共同前缀，直接返回。
该算法时间复杂度大大减少

2.2.1 水平扫描法实现代码

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

三、测试代码

public static void main(String[] args) {
        String[] strs1 = {"hexlo", "helff", "hellx"};
        String[] strs2 = {"hello", "ssss", "wfef"};
        System.out.println(longestCommonPrefix1(strs1));
        System.out.println(longestCommonPrefix1(strs2));
        System.out.println(longestCommonPrefix2(strs1));
        System.out.println(longestCommonPrefix2(strs2));
    }

输出结果为：

he

he