Longest Shared Prefix
Problem
Given a collection of words, find the longest opening run of characters that every word begins with. The run must start at the first character of each word, so a match that appears later in a word does not count. Return the empty text when the words share no opening character.
Examples
Input: words = ["flower", "flow", "flight"]
Output: "fl"
Why: the third word breaks the agreement at the third characterInput: words = ["dog", "racecar"]
Output: ""
Why: the words disagree immediatelyInput: words = []
Output: ""
Why: edge case, there are no words to compareHints
0 / 3
Comparing the words to each other in pairs is more work than you need. The answer can never be longer than any single word, so one word can act as the yardstick.
Line the words up one under another and think in columns rather than in words. The answer ends at the first column where they stop agreeing.
Walk the characters of the first word by position. At each position, check that every other word is long enough and carries the same character there. The first failure ends the prefix at that position, and surviving every position means the whole first word is the prefix.
Solution
The answer can never exceed the first word, so that word serves as a yardstick and the search is over its positions. Scanning column by column stops at the first position where any word is too short or disagrees, which is exactly where the shared prefix ends. Comparing all words at each column, rather than word against word, means the scan stops as early as possible. Time is O(total characters) in the worst case, and space is O(1) beyond the returned slice.
def longest_shared_prefix(words):
if not words:
return ""
for i, ch in enumerate(words[0]): # walk the yardstick word column by column
for word in words[1:]:
if i >= len(word) or word[i] != ch:
return words[0][:i] # this column breaks the agreement
return words[0] # every column survived the check
print(longest_shared_prefix(["flower", "flow", "flight"])) # -> fl
print(longest_shared_prefix(["dog", "racecar"])) # ->
print(longest_shared_prefix([])) # ->Stuck on the idea rather than the code? String Basics covers it.