💬 Discord
Sign In
NeetCode #38LC-14EasyArrays & HashingNC 250
← Back to All Problems

#38 · #14 · Longest Common Prefix(最长公共前缀)

📌 Problem Statement & Constraints

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return the empty string "". Constraints: 1 <= strs.length <= 200, 0 <= strs[i].length <= 200; strings contain only lowercase English letters.

💡 Core Algorithmic Approaches

  1. Vertical scanning: compare the character at position i across all strings. As soon as any string is too short or disagrees, the prefix ends at i.
  2. This is O(S) where S is the total number of characters -- optimal, since you must read the input.
  3. Alternative (elegant): sort the strings. The common prefix of the whole array equals the common prefix of the first and last strings after sorting.
  4. The sorted variant is short but costs O(n log n) comparisons, so vertical scanning is the better answer when asked about complexity.

💻 Benchmark Python3 Implementation

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        first = strs[0]
        for i in range(len(first)):
            ch = first[i]
            for s in strs[1:]:
                # string too short, or character mismatch -> prefix ends here
                if i == len(s) or s[i] != ch:
                    return first[:i]
        return first


# Sorted variant: O(n log n) comparisons but only one string comparison
class Solution2:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        strs = sorted(strs)
        a, b = strs[0], strs[-1]
        i = 0
        while i < len(a) and i < len(b) and a[i] == b[i]:
            i += 1
        return a[:i]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(S) for vertical scanning, where S is the sum of all string lengths -- each character is examined at most once. The sorted variant is O(n log n * k) in the worst case due to string comparisons.
💾 Space Complexity
O(1) extra space for vertical scanning; the sorted variant allocates a sorted copy, so O(n) extra.

⚠️ Interview Pitfalls & Follow-ups

  • Indexing without the length guard: s[i] raises IndexError when a string is shorter than the current prefix position. The check i == len(s) must come first.
  • Assuming all strings are non-empty: the constraints allow strs[i].length == 0, in which case the answer is immediately "" -- the guard above handles it.
  • Starting from the longest string: always iterate over strs[0], since the prefix cannot be longer than any string.
  • Forgetting the strs empty case: LeetCode guarantees strs.length >= 1, but defensive code costs nothing and the sorted variant needs it if you slice.