{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Longest Common Prefix – Solution & Complexity

Interview solutions
/
Longest Common Prefix

Watch: Longest Common Prefix by shrinking the prefix

Start by assuming the first word is the whole prefix. For each following word, while it doesn't start with the prefix, drop the prefix's last character. Once every word has been checked, whatever remains is the longest common prefix — possibly the empty string.

Solution Walkthrough

  1. Step 1: Understanding the Problem

    • Given an array of strings, find the longest common prefix among all strings.
    • If no common prefix exists, return an empty string "".

  2. Step 2: Handle Edge Cases

    • Before proceeding, handle cases where the input list is empty or contains only one string.
      • If the list is empty, return an empty string.
      • If the list has only one string, return that string as the common prefix.
    from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    if not strs:  # Empty list case
        return ""
    if len(strs) == 1:  # Single string case
        return strs[0]

  3. Step 3: Initialize the First String as a Reference Prefix

    • Start by assuming the entire first string in the array is the longest common prefix.
    • We’ll trim this prefix as we compare it to other strings in the array.
    from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    if not strs:
        return ""
    prefix = strs[0]  # Initialize with the first string as reference prefix
    return prefix

  4. Step 4: Iterate Over Each String and Adjust the Prefix

    • Loop through each string in the array (starting from the second string).
    • For each string, compare characters with the current prefix and shorten prefix if characters don’t match.
    from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    if not strs:
        return ""
    prefix = strs[0]
    for string in strs[1:]:
        # While prefix does not match the beginning of string, shorten it
        while not string.startswith(prefix):
            prefix = prefix[:-1]  # Remove the last character from prefix
            if not prefix:
                return ""  # No common prefix found
    return prefix

  5. Step 5: Return the Final Prefix

    • After iterating through all strings and adjusting the prefix, return the final value of prefix.
    • This value represents the longest common prefix shared by all strings in the array.
    from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    if not strs:
        return ""
    prefix = strs[0]
    for string in strs[1:]:
        while not string.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

  6. Step 6: Consider Edge Cases

    • Edge cases include:
      • An array with an empty string, which results in an empty prefix.
      • No common prefix across strings, which should return an empty string.
      • All strings being identical, in which case the common prefix is the string itself.
    from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    if not strs:
        return ""
    prefix = strs[0]
    for string in strs[1:]:
        while not string.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""  # Return empty if no common prefix
    return prefix

FAQ

See also

Practice Longest Common Prefix online (run code in the browser)Alien Dictionary solution (hard)Count Vowels solution (easy)Decode String solution (medium)Decode Ways solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?