LeetCode-14-LongestCommonPrefix

题目摘要

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
所有输入只包含小写字母 a-z

思路

1. 循环比较当前公共前缀和后一个字符串的公共前缀。
2. 如果当前公共前缀为""则停止循环
3. 每次比较两个字符串的如果对应字符不同则停止，之前的即为公共前缀。

代码

class Solution {
    public:
    string res(string str1, string str2){
        int s_size = 0;
        s_size = min(str1.length(),str2.length());
        if (s_size ==0)
        {
            return "";
        }
        for (int i=0;i<s_size;i++)
        {
            // 思路3
            if(str1[i] !=str2[i])
                return str1.substr(0,i);
        }
        if (str1.length() == s_size)
            return str1;
        else 
            return str2;
    }
    public:
    string longestCommonPrefix(vector<string>& strs){
        if(strs.size() == 0)
            return "";
        string strres = strs[0];
        int i=1;
        //思路1
        while(i<strs.size())
        {
            strres = res(strres,strs[i]);
            //思路2
            if (strres.length() == 0)
            {
                return strres;
            }
            i++;
        }
        return strres;
    }
};

转载请注明作者及出处,本文作者为李志伟,本文标题为LeetCode-14-LongestCommonPrefix 本文链接为http://www.lizhiwei.net/LeetCode-14-LongestCommonPrefix.html

赏

谢谢你请我吃糖果

支付宝

微信