Longest Common Prefix
Find the longest string that is a prefix of every word in an array of strings. If there is none, return "".
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] consists of only lowercase English letters if it is non-empty.
Intuition
Longest common prefix finds the longest string that begins every word in an array. The clearest mental model is to stack the words on top of one another and read straight down, one column at a time.
The prefix continues as long as every word has the same letter in the current column. It ends at the first column where any word disagrees — or where any word simply runs out of characters:
- Scan column by column, stopping at the first disagreement or the first word that ends.
That vertical framing has a practical advantage over the alternative of taking the first word and repeatedly trimming it against each other word. The vertical scan stops as soon as it can, so on an input where the words diverge immediately it does almost no work regardless of how long the words are.
The first word bounds the answer — a common prefix cannot be longer than any single word, so looping over strs[0]'s characters covers every possibility.
No accumulator is needed. When column i fails, the answer is strs[0][:i], and if every column succeeds the whole first word is the prefix. Building a character-by-character result works too but is more code for the same outcome.
Watch the empty-array and empty-string cases: an empty input returns "", and a zero-length word forces an immediate stop since it has no column 0.
Vertical scanning: walk column by column across all strings rather than comparing them pairwise. The first disagreement — or the first string that runs out — ends the prefix. This beats sorting or divide-and-conquer for simplicity, and it exits as early as possible, which matters when the common prefix is short.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(S) time and O(1) space.
Scan by column, not by word
Compare character i across all words before moving to i + 1. This stops at the earliest possible moment, unlike trimming a candidate against each word in turn, which processes whole strings before discovering an early mismatch.
Bound the loop by the first word
The common prefix can never exceed any single word, so iterating over strs[0]'s characters covers every candidate length. Any word may end the scan early by being shorter.
Stop on a short word or a mismatch
For each column, if any word has ended or holds a different character, the prefix stops here. Both conditions must be checked — a word shorter than the current column would otherwise be indexed out of bounds.
Return a slice rather than building a string
When column i fails, the answer is strs[0][:i]. If no column fails, the whole first word is the prefix. No accumulator is needed, which removes a class of off-by-one errors.
Handle the empty cases
An empty array returns "". A zero-length word stops the scan at column 0, also giving "" — correct, since nothing can prefix an empty string.
Cost of the vertical scan
In the worst case every character of every word is examined, giving O(total characters) time and O(1) space beyond the returned slice. Early divergence makes the typical case far faster.
Solution & live demo
Common pitfalls
Not checking for a string that ends early
if s[i] != ch:
return strs[0][:i]if i == len(s) or s[i] != ch:
return strs[0][:i]A shorter string raises IndexError before any mismatch is found — ["ab", "a"] crashes rather than returning "a". Running out of characters is itself a terminating condition.
Comparing every pair of strings
for i in range(len(strs)):
for j in range(i + 1, len(strs)):
prefix = common(strs[i], strs[j])for i in range(len(strs[0])):
ch = strs[0][i]
for s in strs[1:]: ...The common prefix of all strings is bounded by the first string, so one column scan against it suffices. Pairwise comparison is quadratic in the number of strings for no gain.
Returning an empty string on a single input
if len(strs) < 2: return ""
return strs[0]
With one string, that string is the longest common prefix of the set. The loop already handles it — the inner loop is empty and the function returns strs[0].
Edge cases
Column 0 immediately runs past it — return "".
Every column matches; the loop finishes and returns the entire first word.
The inner loop has nothing to check; the whole word is trivially the prefix.