Problem 15: Longest Common Prefix

Source: Dev.to

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'])   # → 'fl'
longest_common_prefix(['dog', 'racecar', 'car'])      # → ''
longest_common_prefix(['interspecies', 'interstellar'])  # → 'inters'

The Solution

def longest_common_prefix(strings):
    """
    Finds the longest common prefix among a list of strings.
    """
    # Check for empty input
    if not strings:
        return ""

    # Start with the first string as the initial prefix
    prefix = strings[0]

    # Compare with each subsequent string
    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

Function Definition

def longest_common_prefix(strings):

Defines a function that takes a list of strings.

Empty Input Check

if not strings:
    return ""

Returns an empty string when the input list is empty.

Initial Prefix

prefix = strings[0]

Assumes the whole first string could be the common prefix.

Iterating Over Remaining Strings

for s in strings[1:]:

Loops through each string after the first.

Shrinking the Prefix

while not s.startswith(prefix):
    prefix = prefix[:-1]
    if prefix == "":
        return ""

Repeatedly removes the last character from prefix until the current string starts with it. If prefix becomes empty, there is no common prefix.

Return Result

return prefix

After all strings are processed, prefix holds the longest common prefix.

Example Walkthrough

Example 1: ['flower', 'flow', 'flight']

1. Initialization: prefix = 'flower'
2. Compare with 'flow':
   • 'flow' does not start with 'flower' → prefix = 'flowe'
   • Still mismatched → prefix = 'flow' (now matches)
3. Compare with 'flight':
   • 'flight' does not start with 'flow' → prefix = 'flo'
   • Still mismatched → prefix = 'fl' (now matches)
4. Result: 'fl'

Example 2: ['dog', 'racecar', 'car']

1. Initialization: prefix = 'dog'
2. Compare with 'racecar':
   • Mismatch → prefix = 'do' → mismatch → prefix = 'd' → mismatch → prefix = ''
3. Result: '' (no common prefix)

Key Optimizations

• Horizontal Matching: Start with the maximum possible prefix (the first string) and shrink it only when mismatches are found, rather than checking character by character across all strings.
• Early Escape: As soon as the prefix becomes empty, the algorithm stops, avoiding unnecessary further comparisons.

This approach is simple, readable, and efficient for typical use cases. Happy coding!