Longest Common Prefix

Shrink the candidate prefix word by word

time O(S) where S is total characters across all wordsspace O(1)

The common prefix of all the words can only shrink as you check more words, never grow — so start by assuming the whole first word is the answer, then test that candidate against each other word in turn and chop characters off the end whenever it doesn't fit. Once the candidate is a genuine prefix of every word checked so far, whatever survives to the end is the longest common prefix.

Details

Animated on: Given words=["flower","flow","flight"], find the longest common prefix

Problem:Longest Common PrefixEasy

Shrink the candidate prefix word by word

step 1 / 4

flower

[0]

flow

[1]

flight

[2]

Start with words=["flower","flow","flight"]. Set prefix = strs[0] = "flower".

Pseudocode

1FUNCTION longestCommonPrefix(strs):
2  IF strs is empty: RETURN ''
3  prefix = strs[0]
4  FOR each i from 1 to the length of strs:
5    WHILE prefix is not a prefix of strs[i]:
6      drop the last character of prefix
7      IF prefix is now empty: RETURN ''
8    END WHILE
9  END FOR
10  RETURN prefix
11END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 4 steps

Start with words=["flower","flow","flight"]. Set prefix = strs[0] = "flower".
Compare prefix "flower" with strs[1]="flow". IndexOf check: "flow".indexOf("flower") === -1 (prefix longer than word). Shrink: prefix = prefix.substring(0, 5) = "flowe". Check: "flow".indexOf("flowe") === -1 (still longer). Shrink: prefix = prefix.substring(0, 4) = "flow". Check: "flow".indexOf("flow") === 0, match! prefix is now "flow".
Now compare prefix "flow" with strs[2]="flight". IndexOf check: "flight".indexOf("flow") !== 0 (first char 'f' matches but rest don't). Shrink: prefix = prefix.substring(0, 3) = "flo". Check: "flight".indexOf("flo") !== 0 (f-l-i vs f-l-o, 'o' vs 'i' at index 2). Shrink: prefix = prefix.substring(0, 2) = "fl". Check: "flight".indexOf("fl") === 0, match! prefix is now "fl".
No more words to compare. Final prefix = "fl". All words start with "fl", and no longer prefix exists since "flight" has 'i' at position 2 while "flow" has 'o'.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Common Prefix in the editor All Strings problems Back to roadmap