Longest Common Prefix
Find the longest string that is a prefix of every word in an array of strings. If there is none, return "".
Intuition
Stack the words on top of each other and read straight down, one column at a time. The prefix grows while every letter in the column matches — the first column that disagrees (or runs past a short word) ends it.
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
Vertical scan beats pairwise trimming
You could take the first word and shrink it against each other word, but the cleanest mental model is columnar: compare character i of every word before moving to i+1. The moment any word is too short or has a different letter, the answer is everything before column i.
The first word bounds the answer
The common prefix can never be longer than strs[0], so loop over its characters and test the rest of the words. Early exit does the heavy lifting: with a mismatch in column 0 you do just one pass over the words.
Return a slice, build nothing
No accumulator needed — strs[0][:i] is the prefix when column i fails, and the whole first word is the answer if the loop completes. Worst case touches every character of every word once: O(total characters).
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.