1. Longest Common Prefix (LeetCode)
Model answer
The task
Given a list of strings, return the longest string that is a prefix of every entry. If there is no shared prefix, return an empty string.
Key idea
Compare characters at the same position across all strings, starting from the first string. Stop at the first mismatch or when any string runs out.
Approach
- If the list is empty, return an empty string.
- Scan each character of the first string from left to right.
- For each position, compare that character with the character at the same position in every other string.
- If a string is too short or a character differs, return the matching prefix before that position.
- If all positions match, return the first string.
from typing import List
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
first = strs[0]
for i, char in enumerate(first):
for word in strs[1:]:
if i == len(word) or word[i] != char:
return first[:i]
return first
Complexity:
- Time: O(S), where S is the total number of characters inspected.
- Space: O(1) auxiliary space, excluding the returned prefix.
Common follow-ups
- How would you handle many prefix queries over the same set of strings? Build a trie once, then traverse it to find shared prefixes.
- Could sorting help? Yes. Sort the strings and compare only the first and last; their common prefix is shared by all strings.
- What if strings arrive as a stream? Keep a running prefix and shorten it as each new string arrives.