14 最长公共前缀

🚀 相关链接

LeetCode 14 - 最长公共前缀

📜 描述

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

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

💡 示例

示例 1

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

示例 2

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

📝 提示

1. 1 <= strs.length <= 200
2. 0 <= strs[i].length <= 200
3. strs[i] 如果非空，则仅由小写英文字母组成

💭 思路

通过将字符串数组排序，比较第一个和最后一个字符串的公共前缀，这样可以减少比较的次数，提高效率。

💻 代码实现

public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1) {
            return strs[0];
        }
        List<String> list = Arrays.stream(strs).sorted().toList();
        String s1 = list.getFirst();
        String s2 = list.getLast();

        for (int i = 0; i < s1.length(); i++) {
            String subStr1 = s1.substring(0, i + 1);
            if (!s2.startsWith(subStr1)) {
                return s1.substring(0, i);
            }
        }
        return s1;
    }