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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Common Prefix

Number: 14

Difficulty: Easy

Paid? No

Companies: Google, Meta, Amazon, Bloomberg, Microsoft, Apple, Oracle, Visa, EPAM Systems, Accenture, TikTok, Deloitte, Turing, tcs, Goldman Sachs, Deutsche Bank, Walmart Labs, Zoho, Roblox, PubMatic, Disney, Adobe, Uber, Yahoo, IBM, Jane Street, SAP, Nutanix, Salesforce, Cognizant, American Express, Accolite, PornHub, PhonePe, Yelp

Problem Description

Given an array of strings, find the longest common prefix string amongst them. If there is no common prefix, return an empty string.

Key Insights

  • Compare characters of the strings one column at a time (vertical scanning).
  • The longest possible prefix is limited by the length of the shortest string in the array.
  • As soon as a mismatch is found, the prefix up to that point is the answer.
  • Handle edge cases such as an empty input array or strings with no common prefix.

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) additional space (ignoring output space).

Solution

We use the vertical scanning approach:

  1. If the input array is empty, return an empty string.
  2. Iterate character by character over the first string.
  3. For each character, compare it with the corresponding character in each of the other strings.
  4. If a mismatch or end of any string is encountered, return the substring from the start up to the current index.
  5. If no mismatch is found, the entire first string is the common prefix.

This solution ensures that we only traverse the necessary part of the strings and stops early if a discrepancy is discovered.

Code Solutions

def longestCommonPrefix(strs):
    # If no strings exist, return empty
    if not strs:
        return ""
    # Iterate over each index of the first string
    for i in range(len(strs[0])):
        current_char = strs[0][i]
        # Compare the current character with the corresponding one in the rest of the strings
        for s in strs[1:]:
            # If index exceeds length or characters differ, return the prefix found so far
            if i >= len(s) or s[i] != current_char:
                return strs[0][:i]
    # If no mismatch is found, return the complete first string
    return strs[0]

# Example usage:
print(longestCommonPrefix(["flower", "flow", "flight"]))
← Back to All Questions