C++算法题（最长公共前缀）

2023-06-02 02:32| 来源: 网络整理| 查看: 265

要求：

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

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

原理：依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新到最长公共前缀，当遍历完所有的字符串之后，即可得到字符串数组中的最长公共前缀。

图片演示：

1.首先比较前俩个子字符串

得到公共前缀leet ，再接着比较

还是leet，再比较下一个：

最后得到lee，结束，得到该字符数组的最长公共前缀。

代码实现如下：

class Solution { public: string longestCommonPrefix(vector& strs) { if (!strs.size()) { //判断strs是否为null return ""; } string prefix = strs[0]; //prefix为strs首个子字符串 int count = strs.size(); //strs子字符串个数 for (int i = 1; i < count; ++i) { prefix = longestCommonPrefix(prefix, strs[i]);//进行比较 if (!prefix.size()) { //若为空则无公共前缀 break; } } return prefix; } string longestCommonPrefix(const string& str1, const string& str2) { int length = min(str1.size(), str2.size()); int index = 0; //定义一个为公共前缀总数索引 while (index < length && str1[index] == str2[index]) {//若有字符相等则公共前缀索引加一 ++index; } return str1.substr(0, index); //返回str1中0到index的子字符串，为公共前缀 } };

【本文地址】

公司简介

联系我们