LeetCode刷题（4）～ 最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1:

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

示例 2:

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

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

解答 By 海轰

提交代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
       int len=strs.size();
         string result="";
       if(len==0) return result;
     
       int i=0;
       while(strs[0][i]!='\0')
       {
         for(int j=0;j<len-1;++j)
         {
             if(strs[j][i]!=strs[j+1][i])
             return result;
         }
         result+=strs[0][i];
         ++i;
       }
       return result;
    }
};

运行结果

思路

       对于这道题，海轰采取的简单粗暴的暴力循环。通过题目可以得知，最长公共前缀若存在，则一定在第一个字符串中，所以第一重循环就是对第一个字符串中的每个字符进行，然后一次比较第一个字符串与第二个字符串中的第一个字符，若相同，则比较第二与第三字符串的第一个字符，只有其中有一个不符合，则直接return，反之则将该字符添加至result变量保存即可，最后return 即可。

C++完整测试程序demo

#include <iostream>
#include <vector>
using namespace std;
string longestCommonPrefix(vector<string> &strs)
{
    int len = strs.size();
    string result = "";
    if (len == 0)
        return result;

    int i = 0;
    while (strs[0][i] != '\0')
    {
        for (int j = 0; j < len - 1; ++j)
        {
            if (strs[j][i] != strs[j + 1][i])
                return result;
        }
        result += strs[0][i];
        ++i;
    }
    return result;
}
int main()
{
    // 定义字符数字 动态
    vector<string> a;
    a.push_back("one");
    a.push_back("on");
    a.push_back("one");
    a.push_back("one");
    a.push_back("one");

    // 输入数据
    cout << "最长公共前缀是："<<longestCommonPrefix(a) << endl;

    return 0;
}

运行结果

官方解答

​​官方详解传送门​​

1. 横向扫描
2. 纵向扫描
3. 分治【难点】
4. 二分查找【难点】

方法一：横行扫描

代码实现

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (!strs.size()) {
            return "";
        }
        string prefix = strs[0];
        int count = strs.size();
        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);
    }
};

c++完整测试程序

#include <iostream>
#include <vector>
using namespace std;

//  求两个string 的最长公共前缀
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;
    }
    //返回 str1字符串中 0起始位 长度为index 的字符
    return str1.substr(0, index);
}

string longestCommonPrefix(vector<string> &strs)
{
    if (!strs.size())
    {
        return "";
    }
    string prefix = strs[0];
    int count = strs.size();
    for (int i = 1; i < count; ++i)
    {
        prefix = longestCommonPrefix(prefix, strs[i]);
        // 一旦prefix为空 立即return
        if (!prefix.size())
        {
            break;
        }
    }
    return prefix;
}
int main()
{
    // 定义字符数字 动态
    vector<string> a;
    a.push_back("one");
    a.push_back("on");
    a.push_back("one");
    a.push_back("one");
    a.push_back("one");

    // 输入数据
    cout << "最长公共前缀是：" << longestCommonPrefix(a) << endl;

    return 0;
}