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