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