Longest Common Prefix

Easy · shrink the prefix. Real solution for this problem — same player as the hand-authored deep-dives.

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 14. Longest Common Prefix. The copyrighted prompt is on LeetCode. This page is a working shrink the prefix for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

—Player inputs are capped so the animation stays readable.
—Match LeetCode's own constraints when you submit there.

Examples

Input

strs =: flower flow flight

Output

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Start with the first word, shrink

Assume the first string is the prefix. For every later word, cut the prefix down until it is a prefix of that word.

The answer can only get shorter. The moment it becomes empty, stop.

Algorithm

Seed pref with strs[0].
While the current word does not start with pref, drop the last character of pref.
Return pref.

Time: O(n k)
Space: O(k)

Solution.py

1class Solution:2    def longestCommonPrefix(self, strs: list[str]) -> str:3        if not strs:4            return ""5        pref = strs[0]6        for w in strs[1:]:7            while not w.startswith(pref):8                pref = pref[:-1]9                if not pref:10                    return ""11        return pref

Watch this run

Interactive walkthrough

Playing “Start with the first word, shrink”. Edit the input, hit Run, then scrub.

Approach: Start with the first word, shrink

Loading animation…