Hey everyone! 👋
Today, we're solving a popular string manipulation problem: Longest Common Prefix.
The Problem
The goal is to write a function that finds the longest common prefix among a list of strings.
A prefix is a substring that occurs at the beginning of a string.
The function should return the longest common string that all words in the list start with.
If there is no common prefix, it should return an empty string "".
Examples:
longest_common_prefix(['flower', 'flow', 'flight']) → Should return 'fl'
longest_common_prefix(['dog', 'racecar', 'car']) → Should return "" (no common prefix)
longest_common_prefix(['interspecies', 'interstellar']) → Should return 'inters'
The Solution
Here is the Python implementation:
def longest_common_prefix(strings):
"""
Finds the longest common prefix among a list of strings.
"""
# Check for empty or invalid input
if not strings:
return ""
# Set the first string as the initial prefix
prefix = strings[0]
# Iterate through the remaining strings
for s in strings[1:]:
# Shorten the prefix until it matches the start of the current string
while not s.startswith(prefix):
prefix = prefix[:-1]
# If the prefix becomes empty, there is no common prefix
if prefix == "":
return ""
return prefix
# Test cases
print(longest_common_prefix(['flower', 'flow', 'flight'])) # 'fl'
print(longest_common_prefix(['dog', 'racecar', 'car'])) # ''
print(longest_common_prefix(['interspecies', 'interstellar'])) # 'inters'
Code Breakdown
Let's walk through the code line by line:
def longest_common_prefix(strings):
- Defines a function named
longest_common_prefix that takes a list of words (strings) as input.
if not strings:
Checks if the input list is empty or None.
If it is empty, we return an empty string "".
Note: This is a safer and more Pythonic check than strings is None or strings == 0 limit cases!
prefix = strings[0]
- Sets our initial assumption: let's assume the entire first string is the common prefix.
for s in strings[1:]:
while not s.startswith(prefix):
prefix = prefix[:-1]
if prefix == "":
If we've removed all characters from the prefix, it means the current word shares no common letters at the beginning with our initial assumed prefix.
We immediately return "" as we know there is no common sequence.
return prefix
- Once we've successfully compared our prefix against all strings, the remaining shortened string is safely our longest common prefix!
Example Walkthrough
Let's trace the function with longest_common_prefix(['flower', 'flow', 'flight']):
Initialization:
- Start with
prefix = 'flower'
Compare with 'flow' (First iteration):
'flow' doesn't start with 'flower'? True.
Remove last char: prefix = 'flowe'
'flow' doesn't start with 'flowe'? True.
Remove last char: prefix = 'flow'
'flow' doesn't start with 'flow'? False. Stop while loop.
Current prefix is safely 'flow'.
Compare with 'flight' (Second iteration):
'flight' doesn't start with 'flow'? True.
Remove last char: prefix = 'flo'
'flight' doesn't start with 'flo'? True.
Remove last char: prefix = 'fl'
'flight' doesn't start with 'fl'? False. Stop while loop.
Current prefix is safely 'fl'.
Result: Loop completes, return 'fl'. ✅
Now let's try longest_common_prefix(['dog', 'racecar', 'car']):
Initialization:
- Start with
prefix = 'dog'
Compare with 'racecar':
'racecar' doesn't start with 'dog'? True. Shorten to prefix = 'do'
'racecar' doesn't start with 'do'? True. Shorten to prefix = 'd'
'racecar' doesn't start with 'd'? True. Shorten to prefix = ""
Result: Prefix is empty "". Immediate return "". ❌ No common prefix found.
Key Optimizations
This approach relies heavily on Horizontal Matching:
Shrinking Search Pattern: Instead of checking letter by letter precisely (vertical scaling index-by-index), we start by assuming the maximum possible prefix and aggressively peel off letters from the end whenever mismatches are found.
Early Escape: If the prefix shrinks to an empty string at any point, we completely abort without iterating through the rest of the array strings.
This pattern is highly effective, easy to read, and simple to reason out! 🚀
Happy coding! 💻
