Leet 14 – Longest 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.

My solution:

I will loop on the first string by length, and check each char compared to the rest of the strings, if it is present I will continue and advance the index, lastly I will return the final list from 0 to index.

string longestCommonPrefix(vector<string>& strs) {
    if(strs.size() <2) return "";
    int i = -1;
    while(strs[0][++i])
        for(int j = 1;j < strs.size();j++)
            if(strs[j][i] != strs[0][i]) return strs[0].substr(0,i);
    return strs[0].substr(0,i);
}

Time Complexity:

Worst case O(n) = O(len(string) * len(array_of_string)) happens when all the strings are the same length and are the same characters – because the loop is on every char of each string (len of string(n) * number of strings )

Space Complexity:

O(1) constant – because only several constant number of variables are created.