Pattern visualizer

Longest Common Prefix

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. Animated on: Given words=["flower","flow","flight"], find the longest common prefix.

Shrink the candidate prefix word by word

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

flower

[0]

flow

[1]

flight

[2]

line 3

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

Where to practice Strings

Practice Strings problems All Strings problems Back to roadmap