Leetcode——14. Longest Common Prefix

灰太狼 2022-06-15 11:00 187阅读 0赞

## 1. 概述 ##

Write a function to find the longest common prefix string amongst an array of strings.

题目如上，意思就是在给定的一个字符串数组中，求取所有字符串中的最长公共前缀。

## 2. 编码 ##

### 2.1 方法1 ###

第一种方法是直接拿一个字符串与其它的字符串相比较，记录本次比较重最长公共前缀，遍历完之后就得到了最长的前缀字符串。复杂度是O(N\*M)，N是数组的元素个数，M是取的第一个元素的长度

class Solution {
    public:
        string longestCommonPrefix(vector<string>& strs) 
        {
            int len(strs.size());   //字符串数组中元素的个数
            if(0 == len) return "";
            if(1 == len) return strs[0];
            if(2 == len && strs[0]==strs[1]) return strs[0];      
            
            //方法2
            int pos(0);             //公共字符串的最远端
            string str(strs[0]);    //公共前缀
            
            for(int i=1; i<len; ++i)
            {
                int str_len(str.length()<=strs[i].length()?str.length():strs[i].length());
                
                if(str.length() > strs[i].length())
                {
                    string temp = str;
                    for(int k=0; k<str_len; k++)
                    {
                        if(str.at(k) != strs[i].at(k))
                        {
                            if(0 == k)
                            {
                                str = ""; break;
                            }   //第0个位置就失配了，那就返回空字符串
                            str = str.substr(0, k);
                            break;
                        }
                    }
                    if(str == temp) str = strs[i];
                    continue;
                }
    
                for(int k=0; k<str_len; k++)
                {
                    if(str.at(k) != strs[i].at(k))
                    {
                        if(0 == k)
                        {
                            str = ""; break;
                        }   //第0个位置就失配了，那就返回空字符串
                        str = str.substr(0, k);
                        break;
                    }
                }
            }
            
            return str;
        }
    };

性能

![SouthEast][]

### 2.2 方法2 ###

这里先求取出字符串数组中最短的字符串长度，然后按照这个长度去遍历字符串数组，得到最后的最长公共前缀字符串。O(N\*min\_len)

class Solution {
    public:
        string longestCommonPrefix(vector<string>& strs) 
        {
            int len(strs.size());   //字符串数组中元素的个数
            if(0 == len) return "";
            if(1 == len) return strs[0];
            if(2 == len && strs[0]==strs[1]) return strs[0];
            
            int min_len(123456789); //公共前缀的最大长度
            for(int i=0; i<len; ++i)
            {
                min_len = min(min_len, (int)strs[i].length());
            }
    
            //方法1
            string str(strs[0].substr(0, min_len));    //公共前缀
            for(int i=0; i<len; ++i)
            {
                for(int k=0; k<min_len; ++k)
                {
                    if(str.at(k) != strs[i].at(k))
                    {
                        if(0 == k)
                        {
                            str = ""; break;
                        }   //第0个位置就失配了，那就返回空字符串
                        str = str.substr(0, k);
                        min_len = k;
                        break;
                    }
                }
                if("" == str) break;
            }        
            
            return str;
        }
    };

性能

![SouthEast 1][]

[SouthEast]: /images/20220615/1e7189b57f4f4e23a70f7ae97f54d3ea.png
[SouthEast 1]: /images/20220615/12915e640cce4c51b48b6c31791c5794.png