[Leetcode C++] Longest Common Prefix

Problem:

Write a function to find the longest common prefix string amongst an array of strings.

Solution:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string commPrefix;
        //Case 1: strs is null
        if(strs.empty()) return commPrefix;
        
        for(int i =0; i<strs[0].size(); i++){
            for(int j=1; j<strs.size(); j++){
                //Case 2/3: length issue, or not equal
                if(strs[j].size()<i+1 || strs[j][i]!=strs[0][i])
                    return commPrefix;
            }
            commPrefix.push_back(strs[0][i]);
        }
        return commPrefix;
    }
};

Analysis:

Assume:
m: the number of strings
n: the average length of each string

Then the time complexity is: O(m*n)
The extra space complexity is: O(n)

 

Leave a Reply