Leetcode: Longest Common Prefix

Leetcode Question

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.

Explanation

Naive solution

It’s easy to find the common prefix of two string, the complexity is $O(M*N)$, where M and N is the length of two string.

For finding the common prefix of multiple strings, we start with the common prefix of the first two strings and iterate with the left strings. Just like finding the maximum of multiple values.

The complexity is $O(S * L)$, where S is the number of strings, and L is minimum length of strings.

The performance result is:

file:img/2019_12_03_leetcode-longest-common-prefix.org_20191203_232340.png

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    string common_prefix(string a, string b) {
        string res;
        for(size_t i = 0; i < a.size() && i < b.size(); i++) {
            if(a[i] != b[i]) break;
            res = res + a[i];
        }
        return res;
    }

    string longestCommonPrefix(vector<string> &strs) {
        string ans;
        if(strs.size() == 0)
            return ans;
        ans = strs[0];
        for(size_t i = 1; i < strs.size(); i++) {
            ans = common_prefix(ans, strs[i]);
        }
        return ans;
    }
};

Optimize with sorting

If we sort the array of strings in alphabetically, we only need to find the common prefix of first and last string.

Think about a testcase:

abc ax ab
 ``` after sorted it is:

ab abc ax
common prefix is: common_prefix(“ab”, “ax”) => “a”

The time performance gets much better:

file:img/2019_12_03_leetcode-longest-common-prefix.org_20191203_234532.png

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        if(strs.empty()) return "";
        if(strs.size()==1) return strs[0];
        sort(strs.begin(),strs.end());
        int count=0;
        while(count < strs[0].size() && strs[0][count] == strs[strs.size()-1][count]) 
            count++;            
        return count==0 ? "" : strs[0].substr(0,count);
    }
};

← LeetCode: Remove Nth Node From E... LeetCode: Regular Expression Mat... →