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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)