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; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

运行结果

思路
       对于这道题，海轰采取的简单粗暴的暴力循环。通过题目可以得知，最长公共前缀若存在，则一定在第一个字符串中，所以第一重循环就是对第一个字符串中的每个字符进行，然后一次比较第一个字符串与第二个字符串中的第一个字符，若相同，则比较第二与第三字符串的第一个字符，只有其中有一个不符合，则直接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
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
 

运行结果

官方解答

官方详解传送门

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); }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
 

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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
 

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/107631169