# 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.

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

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 tail = minLen - 1;
{
if (hasCommonPrefix(strs, mid + 1))
else
tail = mid - 1;
}
}

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