LeetCode 每日一题 [19] 最长公共前缀

LeetCode 最长公共前缀 [简单]

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix

示例 1:

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

示例 2:

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

说明

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

题目分析

解法1：

标签：链表
当字符串数组长度为 0 时则公共前缀为空，直接返回
令最长公共前缀 ans 的值为第一个字符串，进行初始化
遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回
时间复杂度：O(s)O(s)，s 为所有字符串的长度之和

作者：guanpengchn
链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/hua-jie-suan-fa-14-zui-chang-gong-gong-qian-zhui-b/
来源：力扣（LeetCode）

解法2：

先把数组进行排序，找到最小和最大的两个字符串，然后从两个字符串中找到结果返回

解法3：

选择一个作为目标字符串，然后逐一进行比较切割，也就是查询此字符串是否包含此字符串，

代码实现

public class LeetCode_19_LongestCommoPrefix {

    public static void main(String[] args) {
        String[] str1 = {"flower", "flow", "flight"};
        String[] str2 = {"dog", "flow", "rececar"};
        System.out.println(longestCommonPrefix(str1));
        System.out.println(longestCommonPrefix(str2));
        System.out.println("=================");
        System.out.println(longestCommonPrefix02(str1));
        System.out.println(longestCommonPrefix02(str2));
        System.out.println("=================");
        System.out.println(longestCommonPrefix03(str1));
        System.out.println(longestCommonPrefix03(str2));
    }

    public static String longestCommonPrefix03(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String prefix = strs[0];
        for (String str : strs) {
            while (str.indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
            }
        }
        return prefix;
    }

    public static String longestCommonPrefix02(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        Arrays.sort(strs);
        String str1 = strs[0];
        String str2 = strs[strs.length - 1];
        int i = 0;
        while (i < str1.length() && i < str2.length() && str1.charAt(i) == str2.charAt(i)) {
            i++;
        }
        if (i == 0) {
            return "";
        } else {
            return str1.substring(0, i);
        }
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            for (; j < ans.length() && j < strs[i].length(); j++) {
                if (ans.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
            }
            ans = ans.substring(0, j);
            if (ans.equals("")) {
                return "";
            }
        }
        return ans;
    }
}