We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Common Prefix

Difficulty: Easy

Problem Description

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".

Key Insights

  • The longest common prefix must be a prefix of all strings in the array.
  • The common prefix can be determined by comparing characters at each index across all strings.
  • If any character does not match at a given index, the longest common prefix ends there.
  • The minimum length among the strings can be used as a boundary for comparison.

Space and Time Complexity

Time Complexity: O(N * M), where N is the number of strings and M is the length of the shortest string. Space Complexity: O(1), as we are using a few variables for tracking the prefix.

Solution

To solve the problem, we can use a simple character-by-character comparison approach. We will iterate through the characters of the first string and compare them with the corresponding characters in the other strings. If we find a mismatch, we will stop and return the prefix formed until that point. If all characters match, we will return the entire first string as the common prefix.

Code Solutions

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    # Start with the first string as the prefix
    prefix = strs[0]
    
    for i in range(len(prefix)):
        for string in strs[1:]:
            # If we reach the end of any string or characters don't match
            if i >= len(string) or string[i] != prefix[i]:
                return prefix[:i]
    
    return prefix
← Back to All Questions