当前位置：首页 > article >正文

力扣题目解析--最长公共前缀

article 2024/11/5 12:01:10

题目

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

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

示例 1：

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

示例 2：

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

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

编者思考

看到这个题目，我的第一反应就是通过双循环暴力破解。我的最初想法是通过三个循环将每一个字符串中的每一个字符进行对比.但是,我忽略了一个问题。就是他对比的应该是前缀。我这样做会产生一个错误就是把他们所有相同的字符全部都集合到一起。而且我在这么做的时候还遇到另外一个问题就是我的结果他会把重复的字符都加进来。我原本苦恼不堪,不知道应该怎么去做。不过我去将这个问题问的AI，我觉得他的解决办法非常值得我思考。在怎样的情况下应该去定义一个类来解决这个问题。当我使用了类去解决这个问题的时候，不单单是循环的数量减少了，而且我也免除了结果重复字符这个问题。因为我的类每一次都会被调用，所以不存在我的结果会不断的积累。

代码展示

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
         if (strs.empty()) {
            return "";
        }

        // 初始化 result 为第一个字符串
        std::string result = strs[0];

        // 从第二个字符串开始，逐个与 result 进行比较
        for (int i = 1; i < strs.size(); ++i) {
            result = commonPrefix(result, strs[i]);
            if (result.empty()) {
                break; // 如果 result 为空，直接返回
            }
        }

        return result;
    }
    private:
    string commonPrefix(const string &str1,const string  &str2){
        int len =min(str1.size(),str2.size());
        string prefix;
        for(int i=0;i<len;++i){
            if(str1[i]==str2[i]){
                prefix+=str1[i];
            }else{
                break;
            }
        }
        return prefix;
    }
};

思想和逻辑

分治法：
- 初始假设：假设最长公共前缀是第一个字符串。
- 逐步验证：从第二个字符串开始，逐个与当前的最长公共前缀进行比较，更新最长公共前缀。
- 提前终止：如果在某次比较中发现没有公共前缀，立即终止并返回空字符串。
贪心算法：
- 局部最优：每次比较两个字符串，找到它们的最长公共前缀。
- 全局最优：通过多次局部最优的选择，最终得到全局最长的公共前缀。

代码逐行解析

检查输入是否为空：
```
if (strs.empty()) {
    return "";
}
```
- 使用 strs.empty() 检查输入的字符串向量是否为空。
- 如果为空，直接返回空字符串 ""。
初始化 result：
```
std::string result = strs[0];
```
- 将 result 初始化为第一个字符串 strs[0]。
遍历字符串向量：
```
for (int i = 1; i < strs.size(); ++i) {
```
- 使用 for 循环从第二个字符串开始遍历字符串向量 strs。
- int i = 1：初始化 i 为 1，从第二个字符串开始。
- i < strs.size()：循环条件，确保 i 不超过字符串向量的大小。
- ++i：在每次循环迭代后增加 i 的值。
更新 result：
```
result = commonPrefix(result, strs[i]);
```
- 调用 commonPrefix 函数，计算当前 result 和 strs[i] 的最长公共前缀。
- 将结果赋值给 result。
检查 result 是否为空：
```
if (result.empty()) {
    break; // 如果 result 为空，直接返回
}
```
- 使用 result.empty() 检查 result 是否为空。
- 如果 result 为空，说明没有公共前缀，直接跳出循环。
返回结果：
```
return result;
```
- 返回最终的最长公共前缀 result。
私有函数 commonPrefix：
```
private:
std::string commonPrefix(const std::string &str1, const std::string &str2) {
```
- 定义一个私有成员函数 commonPrefix，返回类型为 std::string，接受两个字符串的常量引用 str1 和 str2。
计算两个字符串的最小长度：
```
int len = std::min(str1.size(), str2.size());
```
- 使用 std::min 函数计算两个字符串的最小长度 len。
初始化前缀字符串：
```
std::string prefix;
```
- 初始化一个空字符串 prefix，用于存储最长公共前缀。
遍历两个字符串
```
for (int i = 0; i < len; ++i) {
```
- 使用 for 循环遍历两个字符串的前 len 个字符。
- int i = 0：初始化 i 为 0。
- i < len：循环条件，确保 i 不超过最小长度 len。
- ++i：在每次循环迭代后增加 i 的值。
比较字符：
```
if (str1[i] == str2[i]) {
    prefix += str1[i];
} else {
    break;
}
```
- 使用 if 语句比较两个字符串的当前字符 str1[i] 和 str2[i]。
- 如果字符相同，将字符添加到 prefix 中。
- 如果字符不同，跳出循环。
返回前缀：
```
return prefix;
```
- 返回计算得到的最长公共前缀 prefix。