leetcode 14 Longest Common Prefix

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

class Solution {
public:
string longestCommonPrefix(vector<string>& strs)
{

if(strs.size() == 0)
return "";

sort(strs.begin(),strs.end());
int size = strs.size();
int min_size = strs[0].length();
string prefix = "";
for(int i =0;i< min_size;++i)
{
char temp = strs[0][i];
for(int j = 1;j<size;++j)
{
if(strs[j][i]!=temp)
{
//break;
return prefix;
}

}
prefix.append(1,temp); //= prefix +temp;//const char*的话怎么加进去呢？
}

return prefix;
}
};

c++解决方案：

class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
std::sort(strs.begin(),strs.end());
string ans=strs[0];
for (int i = 0; i < strs.size(); ++i)
for (int j = 0; j < ans.length() ; ++j)
{
if(ans[j]!=strs[i][j]) {
ans=ans.substr(0,j);
break;
}
}
return ans;

};

//But when I changed the first loop initial value "int i=1",it cost 8ms. As it is easy to proof the i=0 don't need to compare. //The loop less one time,but cost more than 4ms.

string longestCommonPrefix(vector<string>& strs) {
if(strs.size() == 0)
return "";

string result;
for(int i = 0; i<strs[0].length(); i++) {
char c = strs[0][i];
for(int j = 0; j<strs.size(); j++) {
if(strs[j][i] != c)
return result;
}

result += c;
}

return result;
}

//Divide-and-Conquer Approach, python, 44ms

class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
for (int pos = 0; pos < strs[0].length(); pos++)
for (int i = 1; i < strs.size(); i++)
if (pos >= strs[i].length() || strs[i][pos] != strs[0][pos])
return strs[0].substr(0, pos);
return strs[0];
}
};

class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
int i, j, n = strs.size();
if (n == 0) return "";
sort(strs.begin() ,strs.begin() + n);
for (j = 0; j < strs[0].size() && j < strs[n - 1].size() && strs[0][j] == strs[n - 1][j]; j++);
return strs[0].substr(0, j);
}
};



python解决方案：

class Solution:
# @return a string
def longestCommonPrefix(self, strs):
if not strs:
return ""

for i, letter_group in enumerate(zip(*strs)):
if len(set(letter_group)) > 1:
return strs[0][:i]
else:
return min(strs)

def longestCommonPrefix(self, strs):
prefix = '';
# * is the unpacking operator, essential here
for z in zip(*strs):
bag = set(z);
if len(bag) == 1:
prefix += bag.pop();
else:
break;
return prefix;

#Divide-and-Conquer Approach, python, 44ms

class Solution:
# @param {string[]} strs
# @return {string}

def longestCommonPrefix(self, strs):
if not strs: return ""
total = len(strs)
l = min([len(x) for x in strs])
g = 2
while g / 2 < total:
for i in xrange((total+g-1)/g):
if i*g+g/2 < total:
while l and strs[i*g][:l] != strs[i*g+g/2][:l]: l-=1
g *= 2
return strs[0][:l]

﻿﻿

|
5月前
Leetcode 516. Longest Palindromic Subsequence

22 0
|
5月前
|
Java
Leetcode 3. Longest Substring Without Repeating Characters

27 3
LeetCode 424. Longest Repeating Character Replacem

75 0
LeetCode 409. Longest Palindrome

53 0
LeetCode 395. Longest Substring with At Least K

57 0
|
Windows
LeetCode 388. Longest Absolute File Path

51 0
|

LeetCode 329. Longest Increasing Path in a Matrix

45 0
|

LeetCode 300. Longest Increasing Subsequence

34 0
|

LeetCode 128. Longest Consecutive Sequence

63 0
|
Java 程序员 开发者
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之三：两次优化

82 0