Leetcode 每日一题 14.最长公共前缀

问题描述

给定一个字符串数组strs，我们需要找出这些字符串的最长公共前缀。如果不存在公共前缀，则返回空字符串""。

输入输出格式

• 输入：一个字符串数组strs。
• 输出：一个字符串，表示所有字符串的最长公共前缀。

示例

1. 示例 1：

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

2. 示例 2：

   • 输入：strs = ["dog","racecar","car"]
   • 输出：""

算法分析

解决这个问题的关键在于比较字符串数组中每个字符串的每个字符。我们可以通过以下步骤实现：

1. 确定最短字符串的长度：首先，我们需要找出数组中最短的字符串，因为这将限制最长公共前缀的长度。
2. 逐个字符比较：从第一个字符开始，逐个比较所有字符串在相同位置上的字符是否相同。
3. 更新公共前缀：如果所有字符串在某个位置上的字符都相同，则将该字符添加到公共前缀中。
4. 终止条件：如果在任何位置上发现字符不同，则停止比较，并返回当前已找到的公共前缀。

Java代码实现

java

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        int len = strs[0].length(); // 确定最短字符串的长度
        for (int i = 0; i < strs.length; i++) {
            if (len > strs[i].length()) {
                len = strs[i].length();
            }
        }
        
        String s = ""; // 存储公共前缀
        for (int i = 0; i < len; i++) {
            char currentChar = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (strs[j].charAt(i) != currentChar) {
                    return s; // 一旦发现字符不同，返回当前公共前缀
                }
            }
            s += currentChar; // 将匹配的字符添加到公共前缀
        }
        
        return s; // 返回完整的公共前缀
    }
}

代码解析

1. 边界条件处理：首先检查输入数组是否为空或为null，如果是，则直接返回空字符串。
2. 确定最短字符串长度：通过遍历数组，找出最短的字符串，以确定比较的最大长度。
3. 逐个字符比较：使用两层循环，外层循环遍历每个字符位置，内层循环比较该位置上的字符是否相同。
4. 更新公共前缀：如果所有字符串在某个位置上的字符相同，则将该字符添加到结果字符串s中。
5. 返回结果：如果完成所有字符的比较，返回完整的公共前缀；如果在任何位置发现不同的字符，返回当前已找到的公共前缀。

原文地址：https://blog.csdn.net/weixin_73687229/article/details/143720881

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！