Leetcode 14. Longest Common Prefix

Problem

Given an array of strings, find the longest string that is a common prefix shared by all strings in the array. If no common prefix exists, return an empty string.

A prefix is a substring that appears at the beginning of each string. For example, "pre" is a prefix of "prefix" and "prepare", but not of "suppose".

Requirements

1. Return the longest prefix that appears at the start of every string in the input array
2. If there is no common prefix among all strings, return an empty string ""
3. The comparison should be case-sensitive
4. Handle edge cases such as empty arrays or arrays with a single string

Constraints

• 0 ≤ words.length ≤ 200
• 0 ≤ words[i].length ≤ 200
• words[i] consists of only lowercase English letters
• Time complexity should be O(S) where S is the sum of all characters in all strings
• Space complexity should be O(1) excluding the output

Examples

Example 1:

Input: words = ["flower", "flow", "flight"] Output: "fl" Explanation: The prefix "fl" is common to all three words.

Example 2:

Input: words = ["dog", "racecar", "car"] Output: "" Explanation: There is no common prefix among the input strings.

Example 3:

Input: words = ["interstellar", "internet", "interval"] Output: "inter" Explanation: All three words start with "inter".

Example 4:

Input: words = ["single"] Output: "single" Explanation: With only one word, the entire word is the common prefix.

Hint 1: Finding the Limit Consider what determines the maximum possible length of the common prefix. Can the common prefix be longer than the shortest string in the array?

Hint 2: Character-by-Character Comparison Think about comparing characters at the same position across all strings. What should happen when you find the first mismatch at a particular position?

Hint 3: Early Termination You can stop early if you find any mismatch or reach the end of any string. This avoids unnecessary comparisons.

Full Solution ` def longestCommonPrefix(words): # Handle edge cases if not words: return ""

if len(words) == 1:
    return words[0]

# Find the minimum length among all strings
# The common prefix cannot be longer than the shortest string
min_length = min(len(word) for word in words)

# Compare characters at each position across all strings
for i in range(min_length):
    # Get the character at position i from the first string
    current_char = words[0][i]
    
    # Check if all other strings have the same character at position i
    for word in words[1:]:
        if word[i] != current_char:
            # Found a mismatch, return prefix up to this point
            return words[0][:i]

# If we've checked all positions up to min_length without mismatch,
# the common prefix is the entire shortest string
return words[0][:min_length]

`

Approach:

The solution uses a vertical scanning approach:

1. Handle Edge Cases: First check if the array is empty (return "") or has only one element (return that element).

2. Find Minimum Length: Determine the shortest string length since the common prefix cannot exceed this length.

3. Character-by-Character Comparison: For each position from 0 to the minimum length:

   • Take the character at that position from the first string as reference
   • Compare it with the character at the same position in all other strings
   • If any mismatch is found, return the substring up to (but not including) the current position

4. Complete Match: If all positions up to the minimum length match, the entire shortest string is the common prefix.

Time Complexity: O(S) where S is the sum of all characters in all strings. In the worst case, we compare every character once.

Space Complexity: O(1) for the algorithm itself, not counting the output string. We only use a few variables for tracking position and current character.

Alternative Approach: You could also sort the array and compare only the first and last strings lexicographically, since the common prefix of all strings must be a prefix of both the lexicographically smallest and largest strings. This would have O(S + n log n) time complexity where n is the number of strings.