How do you find the longest common prefix of a list of strings, and what is the complexity?
You look at each character position in turn, and you keep going while all of the strings have the same letter there.
def longest_common_prefix(words):
if not words:
return ""
shortest = min(words, key=len)
for index in range(len(shortest)):
letter = shortest[index]
for word in words:
if word[index] != letter:
return shortest[:index]
return shortest
So how does it work? You start with the shortest string, because the prefix cannot be longer than that one. Then you go through its character positions one at a time. At each position you check that every other string has the same letter there. The first position where they disagree is where the prefix ends, and everything before it is the answer.
And the complexity is O of n times m for the time, where n is the number of strings and m is the length of the shortest one. You might look at every string at every position, but you stop at the position where they disagree, so the real work is usually much less than that.
The next question in this topic shows the same idea written the other way round, which is often the version to write in an interview.