寻找公共前缀

最新推荐文章于 2024-03-26 11:23:38 发布

妖怪喜欢风

最新推荐文章于 2024-03-26 11:23:38 发布

阅读量680

点赞数 1

分类专栏：计算机四大力柱文章标签： leetcode c++

本文链接：https://blog.csdn.net/qq_48322523/article/details/111604483

版权

计算机四大力柱专栏收录该内容

74 篇文章

订阅专栏

本文分享了两种高效算法，一种时间复杂度为O(n²)，空间复杂度为O(n²)，通过逐个字符对比；另一种优化版本在O(n)时间内完成，空间复杂度为O(n)，通过先排序再比较。两种方法对比，提升编程技巧。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

今天看到一个好赞的题目！！！分享一波

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

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

大佬的解法
执行时间m/s，
时间复杂度：T(n²)
空间复杂度：O(n²)

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
    // 判断数组是否为空，若为空则返回空值，否则返回数组的第一个元素作为基数
        string res = strs.empty() ? "" : strs[0]; 
        for (string s : strs) 
        /*
        获得数组的每一个元素，用find函数获得基数在每一个元素
        的首地址，若某一个元素中不存在这个元素或地址不为0，
        位数往前进一，此时分为两种情况：
        1.若基数为flws，元素为fl，则一次次的while循环往前
        进一中是可以找到公共前缀的。
        2.若基数为flws，元素为sd，则一次次的while循环往前进一
        中仍然找不到最终为0退出循环。
		*/
            while (s.find(res) != 0) res = res.substr(0, res.length() - 1);
        return res;
    }
};

其实我个人更喜欢另外一种解法
执行时间0m/s
时间复杂度：T(n)
空间复杂度：O(n)

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res="";
        int n=strs.size();
        if(n==0)
            return res;
        if(n<2)
            return strs[0];
        // 此处对数组进行排序，按照字符a-z从小到大排序
        sort(strs.begin(),strs.end());
        for(int i=0;i<strs[0].size();i++)
        {
        	// 取第一个和最后一个字符串即可
            if(strs[0][i]==strs[n-1][i])
            {
                res+=strs[0][i];
                continue;
            }
            break;
        }
        return res;
    }
};