# 14. 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:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
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.
# Solution
Approach 1: Horizontal scanning.
Approach 2: Vertical scanning.
Approach 3: Divide and conquer.
Approach 4: Binary search.
# Code (Python)
Approach 1:
Approach 2:
Approach 3:
Approach 4:
# Code (C++)
Approach 1:
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) return "";
string prefix = strs[0];
for (int i = 1; i < strs.size(); ++i)
{
for (int j = 0; j < prefix.size(); ++j)
{
if (strs[i].size() == j || strs[i][j] != prefix[j]) // Need to check the size of strs[i].
{
prefix = prefix.substr(0, j);
break;
}
}
}
return prefix;
}
};
Approach 2:
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) return "";
for (int i = 0; i < strs[0].size(); i++)
{
for (int j = 1; j < strs.size(); ++j)
{
if (strs[j].size() == i || strs[j][i] != strs[0][i]) // Need to check the size of strs[j].
return strs[0].substr(0, i);
}
}
return strs[0];
}
};
Approach 3:
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
return longestCommonPrefix(strs, 0, strs.size() - 1);
}
private:
string longestCommonPrefix(vector<string>& strs, int head, int tail) {
if (head > tail) return "";
if (head == tail) return strs[head];
int mid = head + (tail - head) / 2;
string left = longestCommonPrefix(strs, head, mid);
string right = longestCommonPrefix(strs, mid + 1, tail);
for (int i = 0; i < left.size(); ++i)
{
if (right.size() == i || right[i] != left[i]) // Need to check the size of right.
return left.substr(0, i);
}
return left;
}
};
Approach 4:
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) return "";
int minLen = strs[0].size();
for (int i = 1; i < strs.size(); ++i)
{
if (strs[i].size() < minLen) minLen = strs[i].size();
}
int head = 0;
int tail = minLen - 1;
while (head <= tail)
{
int mid = head + (tail - head) / 2;
if (hasCommonPrefix(strs, mid + 1))
head = mid + 1;
else
tail = mid - 1;
}
return strs[0].substr(0, head);
}
private:
bool hasCommonPrefix(vector<string>& strs, int len)
{
int i = 0;
for (; i < len; ++i)
{
int j = 1;
for (; j < strs.size(); ++j)
{
if (strs[j][i] != strs[0][i]) break;
}
if (j < strs.size()) break;
}
if (i == len)
return true;
else
return false;
}
};