【LeetCode】14. 最长公共前缀

我会带着你远行 2022-05-08 15:42 74阅读 0赞

**题目链接**：[https://leetcode-cn.com/problems/longest-common-prefix/description/][https_leetcode-cn.com_problems_longest-common-prefix_description]

#### 题目描述 ####

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

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

#### 示例 ####

输入: \[“flower”,“flow”,“flight”\]  
输出: “fl”

输入: \[“dog”,“racecar”,“car”\]  
输出: “”  
解释: 输入不存在公共前缀。

**说明**:

所有输入只包含小写字母 a-z 。

#### 解决方法 ####

题目较简单

class Solution { 
    public:
        string longestCommonPrefix(vector<string>& strs) { 
            string result="";
            if (strs.size()==0) return result; //特殊情况
            
            int maxLen=-1;
                for (int j=0;j<strs[0].size();j++){ 
                    string subStr=strs[0].substr(0,j+1);
                    //判断子串subStr是否是公共前缀
                    bool flag=true;
                    for (int k=1;k<strs.size();k++){ 
                        if (strs[k].find(subStr)!=0){ 
                            flag=false;
                            break;
                        }
                    }
                    //subStr是公共前缀
                    if (flag){ 
                        int temp=subStr.size();
                        if (temp>maxLen){ 
                            maxLen=temp;
                            result=subStr;
                        }
                    }
                    //subStr不是公共前缀
                    else break;
                }
    
            
            return result;
        }
    };

[https_leetcode-cn.com_problems_longest-common-prefix_description]: https://leetcode-cn.com/problems/longest-common-prefix/description/