Problem 15: Longest Common Prefix

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:

1. def longest_common_prefix(strings):

   • Defines a function named longest_common_prefix that takes a list of words (strings) as input.

2. 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!

3. prefix = strings[0]

   • Sets our initial assumption: let's assume the entire first string is the common prefix.

4. for s in strings[1:]:

   • Iterates through each subsequent string (s) in the list.
   • strings[1:] is Python slice notation that means "all elements from index 1 to the end".

5. while not s.startswith(prefix):

   • Keeps running as long as the current string s doesn't start with our assumed prefix.
   • .startswith() checks if a string begins with the specified prefix.

6. prefix = prefix[:-1]

   • Removes the last character from the prefix to make it shorter.
   • prefix[:-1] is string slicing that takes all characters except the last one.

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

8. 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']):

1. Initialization:
   • Start with prefix = 'flower'
2. 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'.
3. 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'.
4. Result: Loop completes, return 'fl'. ✅

Now let's try longest_common_prefix(['dog', 'racecar', 'car']):

1. Initialization:
   • Start with prefix = 'dog'
2. 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 = ""
3. 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! 💻