28
03/2015
[LeetCode] Longest Common Prefix
Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
解题思路：
注意string类的append和push_back方法的使用。
1. 先求两个字符串的前缀，在求此前缀与剩下的字符串的前缀。代码如下：
class Solution {
public:
string longestCommonPrefix(vector<string> &strs){
string result = "";
int count = strs.size();
if (count == 0){
return "";
}
if (count == 1){
return strs[0];
}
result = commonPrefix(strs[0], strs[1]);
for (int i = 2; i < count; i++){
if (result == ""){
break;
}
result = commonPrefix(result, strs[i]);
}
return result;
}
private:
string commonPrefix(string& s1, string& s2){
int len1 = s1.length();
int len2 = s2.length();
int len = len1 < len2 ? len1 : len2;
string result = "";
for (int i = 0; i < len; i++){
if (s1[i] == s2[i]){
result.append(1, s1[i]);
}
else{
break;
}
}
return result;
}
};2. 逐位比较所有字符串，若遇到不全相等的位，停止比较。这种方法效率更高。代码如下：
class Solution {
public:
string longestCommonPrefix(vector<string> &strs){
string result = "";
int count = strs.size();
if (count == 0){
return "";
}
int minLen = strs[0].length();
for (int i = 1; i < count; i++){
if (minLen > strs[i].length()){
minLen = strs[i].length();
}
}
for (int i = 0; i < minLen; i++){
char c = strs[0][i];
int j = 1;
for (; j < count; j++){
if (strs[j][i] != c){
break;
}
}
if (j == count){
result.append(1, c);
}else{
break;
}
}
return result;
}
};二次刷题（update in 2015-07-30）
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string result = "";
int len = strs.size();
if(len == 0){
return result;
}
for(int i=0; i<strs[0].length(); i++){
bool bMatch = true;
for(int j = 1; j < len; j++){
if(i>=strs[j].length() || strs[j][i] != strs[0][i]){
bMatch = false;
break;
}
}
if(bMatch){
result += strs[0][i];
}else{
break;
}
}
return result;
}
};转载请注明：康瑞部落 » [LeetCode] Longest Common Prefix
0 条评论