14

14. Longest Common Prefix (Easy)

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: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

Companies:
Amazon, Facebook, Adobe, Apple, Snapchat, Google, Bloomberg, Microsoft, Yahoo, Uber, Paypal, Intel

Related Topics:
String

Solution 1. Horizontal Scanning

// OJ: https://leetcode.com/problems/longest-common-prefix/
// Author: github.com/lzl124631x
// Time: O(NW)
// Space: O(1)
class Solution {
public:
    string longestCommonPrefix(vector<string>& A) {
        int len = A[0].size();
        for (int i = 1; i < A.size() && len; ++i) {
            int j = 0, end = min(len, (int)A[i].size());
            while (j < end && A[0][j] == A[i][j]) ++j;
            len = j;
        }
        return A[0].substr(0, len);
    }
};

Solution 2. Vertical Scanning

// OJ: https://leetcode.com/problems/longest-common-prefix/
// Author: github.com/lzl124631x
// Time: O(NW)
// Space: O(1)
class Solution {
public:
    string longestCommonPrefix(vector<string>& A) {
        int len = 0, N = A.size();
        for (; len <= A[0].size(); ++len) {
            int i = 1;
            for (; i < N && A[i].size() >= len && A[i][len] == A[0][len]; ++i);
            if (i < N) break;
        }
        return A[0].substr(0, len);
    }
};