LeetCode 面试经典 150_数组/字符串_最长公共前缀（20_14_C++_简单）(暴力破解)(求交集)

题目描述：

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

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

输入输出样例：

示例 1：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”

示例 2：
输入：strs = [“dog”,“racecar”,“car”]
输出：“”
解释：输入不存在公共前缀。

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

题解：

解题思路：

思路一（暴力破解）：

1、首先检查字符串数组的第一个元素是否为空。如果为空，直接返回空字符串，因为不存在公共前缀。每次遍历所有字符串，每趟遍历核对一个字符(第一趟核对第一个字符，第二趟核对第二个字符…)。如果本趟循环中所有的字符串都含有该字符，则添加到答案字符串中。
例：strs = [“flower”,“flow”,“flight”]
① 确定 “f” 为公共字符，ans=“f”。
② 确定 “l” 为公共字符，ans=“fl”。
③ 无公共字符，ans=“fl”。

2、复杂度分析：
① 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
② 空间复杂度：O(1)。使用的额外空间复杂度为常数。

思路二（求交集）：

1、将字符串每个字符串进行两两合并最长公共前缀，合并出的字符串再和下一个元素进行合并。
例：strs = [“flower”,“flow”,“flight”]
① “flower” 和 “flow” 的公共前缀为 “fl”。
② “fl” 和 “flight” 的公共前缀为 “fl”。
③ ans=“fl”。

2、复杂度分析
① 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
② 空间复杂度：O(1)。使用的额外空间复杂度为常数。

代码实现

代码实现（思路一（暴力破解））：

class Solution1 {
public:
    // 该函数返回字符串数组中所有字符串的最长公共前缀
    string longestCommonPrefix(vector<string>& strs) {
        // 如果第一个字符串为空，则没有公共前缀，直接返回空字符串
        if (strs.size()==0){
            return "";
        }
        
        // 初始化ans为空字符串，用于存储公共前缀
        string ans=""; 
        char c;
        
        // 循环遍历第一个字符串的每个字符
        for (int i = 0; i < strs[0].size(); i++){
            // 获取当前字符
            c = strs[0][i];
            
            // 遍历所有字符串，检查当前字符是否在所有字符串的同一位置上
            for (int j = 0; j < strs.size(); j++){
                // 如果当前字符串的长度小于等于i，或者当前字符不相同
                if (strs[j].size() <= i || strs[j][i] != c){
                    // 如果找到不同的字符或长度不够，则返回已找到的公共前缀
                    return ans;
                }
            }
            
            // 如果所有字符串的当前字符相同，则将字符添加到公共前缀ans中
            ans += c;
        }
        
        // 返回最终的最长公共前缀
        return ans;
    }
};

代码实现（思路二（求交集））：

class Solution2 {
private:
    // merge 函数用于返回两个字符串的公共前缀
    string merge(const string &str1, const string &str2){
        // 计算两个字符串中较短的长度
        int length = min(str1.size(), str2.size());
        
        // 遍历两个字符串的字符，找到第一个不同的字符
        for (int i = 0; i < length; i++){
            // 如果字符不同，返回第一个字符串到当前字符位置的子串作为公共前缀
            if (str1[i] != str2[i]){
                return str1.substr(0, i);
            }
        }
        
        // 如果没有找到不同字符，返回较短的字符串作为公共前缀
        return str1.substr(0, length);
    }

public:
    // 主函数，用来返回多个字符串的最长公共前缀
    string longestCommonPrefix(vector<string>& strs) {
        // 如果输入的字符串数组为空，返回空字符串
        if (strs.size() == 0){
            return "";
        }

        // 将第一个字符串作为初始的公共前缀
        string ans = strs[0];
        
        // 遍历数组中的剩余字符串，逐一与当前的公共前缀进行合并
        for (int i = 1; i < strs.size(); i++){
            // 合并当前前缀和下一个字符串
            ans = merge(ans, strs[i]);

            // 如果公共前缀已经为空，提前退出
            if (ans.size() == 0){
                break;
            }
        }
        
        // 返回最终的最长公共前缀
        return ans;
    }
};

以思路一为例进行调试

#include<iostream>
#include<vector>
using namespace std;

class Solution1 {
public:
    // 该函数返回字符串数组中所有字符串的最长公共前缀
    string longestCommonPrefix(vector<string>& strs) {
        // 如果第一个字符串为空，则没有公共前缀，直接返回空字符串
        if (strs.size()==0){
            return "";
        }
        
        // 初始化ans为空字符串，用于存储公共前缀
        string ans=""; 
        char c;
        
        // 循环遍历第一个字符串的每个字符
        for (int i = 0; i < strs[0].size(); i++){
            // 获取当前字符
            c = strs[0][i];
            
            // 遍历所有字符串，检查当前字符是否在所有字符串的同一位置上
            for (int j = 0; j < strs.size(); j++){
                // 如果当前字符串的长度小于等于i，或者当前字符不相同
                if (strs[j].size() <= i || strs[j][i] != c){
                    // 如果找到不同的字符或长度不够，则返回已找到的公共前缀
                    return ans;
                }
            }
            
            // 如果所有字符串的当前字符相同，则将字符添加到公共前缀ans中
            ans += c;
        }
        
        // 返回最终的最长公共前缀
        return ans;
    }
};

int main(int argc, char const *argv[])
{
    vector<string> strs={"dog","dacecar","dar"};
    Solution1 s;
    cout<<s.longestCommonPrefix(strs);
    return 0;
}

LeetCode 面试经典 150_数组/字符串_最长公共前缀（20_14)原题链接
欢迎大家和我沟通交流(✿◠‿◠)