LeetCode14. Longest Common Prefix

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

If there is no common prefix, return an empty string "".

Example 1:

1
2
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.


sort+bf

Sort

思路

将容器里的string排序,有共同字母多的两个字符串会被排到一起,而跟其它字符串相同的字母越少的string会被挤到容器首尾两端,最后找首尾字母串的共同前缀。

My code in cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty())//1.
return "";
sort(strs.begin(), strs.end());
vector<char> ret;
string first = *strs.begin();
string last = strs.back();
int m = first.size(), n = last.size();
for(int i=0,j=0;i<m&&j<n;i++,j++)
{
if (first[i] != last[i])
break;
ret.push_back(first[i]);
}
string res = "";
for (auto const & c : ret)
res += c;
return res;
}

Detail

  1. 一定要记得做入口判断,不然传[]进去,后面的函数编译器都用不了的,会报错。

lc in cpp

1
2
3
4
5
6
7
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
sort(strs.begin(), strs.end());
int i = 0, len = min(strs[0].size(), strs.back().size());
while (i < len && strs[0][i] == strs.back()[i]) ++i;
return strs[0].substr(0, i);
}

Brute-force

思路

将容器的string转换成2D array。纵向遍历。

my code in cpp

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
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty())
return "";
vector<char> ret;

vector<vector<char>> _2DArray;
//1.
for (auto const & string : strs)
{
vector<char> array;
for(auto const & c :string)
{
array.push_back(c);
}
_2DArray.push_back(array);
}

for (int col = 0,row= 0;
col< _2DArray[0].size(); col++)//cols
{
char cur = _2DArray[row][col];
for (; (row < _2DArray.size()); row++)//rows
{
if (strs[row].length() <= col
||_2DArray[row][col] != cur)//2.
break;
}
if(row==_2DArray.size())
ret.push_back(cur);
else break;//3.
row = 0;//4.
}

string res = "";
for (auto const & c : ret)
res += c;
return res;
}

细节

  1. string to vector<char>
  2. vector越界:strs[row].length() <= col|| 。而且要在||前面
  3. else break;:如果出现[“aca”,”cba”],会返回a。加了else之后就不会继续遍历了。遇到不符合prefix的string就直接break.
  4. vector越界:每遍历完一列后,要把row置为0.

lc in cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
string res = "";
for (int j = 0; j < strs[0].size(); ++j) {
char c = strs[0][j];
for (int i = 1; i < strs.size(); ++i) {
if (j >= strs[i].size() || strs[i][j] != c) {
return res;
}
}
res.push_back(c);
}
return res;
}

Brute-force 优化substr

my code in cpp

1
2
3
4
5
6
7
8
9
10
11
12
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
for(int col=0;col<strs[0].size();col++)
{
for(int row=0;row<strs.size();row++)
{
if(strs[row].size()<=col||strs[row][col]!=strs[0][col])
return strs[0].substr(0,col);//1.
}
}
return strs[0];//2.如果前面没有return说明第一个string就是最长prefix
}

总结

  1. 用sort很难想到,但是写出来很简单。
  2. 2Darray的纵向遍历有点难想到,写出来的时候细节很多,尤其是数组越界。看了别人的写法之后,我才知道vector<string>本身就是2Darray,直接用[]重载就行,根本不用转换vector<char>。而且用return res代替break就可以少在外面的for loop里面做break了。
  3. 用substr更简单,如果遇到不匹配的,不用break,直接return strs[0].substr(0,col)。就不需要容器了。
Thanks for Support.