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

• ``````# 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.

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