Python recursive boring solution (linear time, and constant space) with simple explanation


  • 1
    # asymptotic O(n*m) (n=number of words, m=number of letters) time, and O(1) space complexity
    class Solution(object):
        def longestCommonPrefix(self, strs):
            if not strs:
                return ''
            first_word = strs[0]
            for i in range(len(first_word)):
                for j in range(1,len(strs)):
                    if i >= len(strs[j]): # first_word larger than current_word
                        return first_word[:i]
                    if strs[j][i] != first_word[i]: # letters don't equal
                        return first_word[:i]
    
            return first_word # made it to the end of the first word so this the common prefix
    

    Explanation: No sorting (which adds additional O(nlogn) complexity) needed. The letters of the first word in the strs list will be used to compare against the letters of all of the other strings in the list. There are two main comparison cases while iterating over the letters of the first word: 1) The current index of the first word is larger then current index of the word being compared against. 2) The current first word letter does not match the letter in the word being compared against. In both cases, just return the substring of the first word up until this index. If you make it though the entire first word, then the entire first word is the common prefix.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.