丰县建设局规划局网站,零食网页制作素材,免费空间访客领取网站,wordpress5.0后台慢题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀#xff0c;返回空字符串 。 示例 1#xff1a;
输入#xff1a;strs [flower,flow,flight]
输出#xff1a;fl示例 2#xff…题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀返回空字符串 。 示例 1
输入strs [flower,flow,flight]
输出fl示例 2
输入strs [dog,racecar,car]
输出
解释输入不存在公共前缀。 提示
1 strs.length 2000 strs[i].length 200strs[i] 仅由小写英文字母组成
编者思考
看到这个题目我的第一反应就是通过双循环暴力破解。我的最初想法是通过三个循环将每一个字符串中的每一个字符进行对比.但是,我忽略了一个问题。就是他对比的应该是前缀。我这样做会产生一个错误就是把他们所有相同的字符全部都集合到一起。而且我在这么做的时候还遇到另外一个问题就是我的结果他会把重复的字符都加进来。我原本苦恼不堪,不知道应该怎么去做。不过我去将这个问题问的AI我觉得他的解决办法非常值得我思考。在怎样的情况下应该去定义一个类来解决这个问题。当我使用了类去解决这个问题的时候不单单是循环的数量减少了而且我也免除了结果重复字符这个问题。因为我的类每一次都会被调用所以不存在我的结果会不断的积累。
代码展示 class Solution {
public:string longestCommonPrefix(vectorstring 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 i0;ilen;i){if(str1[i]str2[i]){prefixstr1[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。
