Core idea: the longest common prefix (LCP) of a set of strings is associative —
LCPof the whole equals theLCPof theLCPs of its parts. That single fact lets you scan column-by-column or split the list in half and conquer.
Problem, rephrased
You're given a list of strings strs. Return the longest string that every one of them starts with. If they share no leading character at all, return the empty string "".
Think of the strings stacked on top of each other, left-aligned. Read straight down column 0 — if every string has the same character there, that character is in the prefix. Move to column 1, and so on. The moment a column disagrees (or you run off the end of the shortest string), you stop. Whatever you collected to the left is the answer.
strs |
Stacked, aligned left | LCP |
|---|---|---|
["flower", "flow", "flight"] |
flower / flow / flight |
"fl" |
["dog", "racecar", "car"] |
dog / racecar / car |
"" |
["interspecies", "interstellar", "interstate"] |
all start inters… |
"inters" |
["throne", "throne"] |
identical | "throne" |
["ab", "abc", "abcd"] |
ab is a prefix of the rest |
"ab" |
Notice the second row: dog and racecar already disagree at column 0, so the answer is "" — common prefixes are unforgiving, one outlier kills everything. And the last row shows the subtle case the answer is bounded by the shortest string.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson