Longest Common Prefix

Mar 5, 2020 by Kevin Nasto

Description

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

Space and Time Complexity

Since we aren’t storing anything the space complexity is O(1). The time complexity is O(mn) where m is the number of letters in the common prefix and n is the number of strings. We are checking letter by letter (only if it matches) for every string.

def check_letter(idx, letter, min_len, strs):
    for string in strs:
        if idx >= min_len:
            return False
        if letter != string[idx]:
            return False
    return True

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ''
        min_len = min([len(x) for x in strs])
        prefix = []
        first_string = strs[0]
        for idx, letter in enumerate(first_string):
            if check_letter(idx, letter, min_len, strs):
                prefix.append(letter)
            else:
                break
        return ''.join(prefix)

Javascript Solution by Akira957

var longestCommonPrefix = function(strs) {
     if(!strs.length){
        return ''
    }
    let firstStr=strs.shift()
    if(!strs.length){
        return firstStr
    }
    
    let isFound=false
    let str=firstStr
    
        for(var j=firstStr.length;j>0;j--){
            str=firstStr.slice(0,j)
            isFound=strs.every((item)=>{
                return item.indexOf(str)==0
            })
            if(isFound){
                return str
            }
        }
    return ''
};