LeetCode #14 Easy

Longest Common Prefix

Find the longest string that is a prefix of every word in an array of strings. If there is none, return "".

stringscan

02

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.

03

Approach

1

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.

2

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.

3

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).

04

Solution & live demo

python

▶1class Solution:
▶2    def longestCommonPrefix(self, strs):
▶3        for i in range(len(strs[0])):
▶4            ch = strs[0][i]
▶5            for s in strs[1:]:
▶6                if i == len(s) or s[i] != ch:
▶7                    return strs[0][:i]
▶8        return strs[0]

05

Edge cases

A word is empty

Column 0 immediately runs past it — return "".

All words identical

Every column matches; the loop finishes and returns the entire first word.

Single word in the array

The inner loop has nothing to check; the whole word is trivially the prefix.

06

Complexity

Time

O(S)

Space

O(1)

S = total characters across all words; the slice at the end is at most the shortest word.