Longest Common Prefix

easyTrie & Strings23 stepsJava · Python · C++

Find the longest prefix shared by every string. Compare column by column: take each character of the first string and check that every other string has the same character at that position. Stop at the first mismatch or when a string runs out.

▶ Watch the animated trace

Traced input: strs = [flower, flow, flight] → "fl". Original problem: neetcode.io/problems/longest-common-prefix

Complexity

BestO(n)

AverageO(S)

WorstO(S)

SpaceO(1)

S = total characters; stops at the first mismatching column.

Key idea

The answer can't be longer than the shortest string.
Check column i across all strings before moving to column i + 1.
Sorting and comparing only the first and last strings is a neat alternative.

Common mistakes

Not handling an empty string in the list (answer "").
Index out of range when a later string is shorter than the first.

Solution

Java

String longestCommonPrefix(String[] strs) {
    String first = strs[0];
    for (int i = 0; i < first.length(); i++) {
        char c = first.charAt(i);
        for (int k = 1; k < strs.length; k++) {
            if (i == strs[k].length() || strs[k].charAt(i) != c) {
                return first.substring(0, i);
            }
        }
    }
    return first;
}

Python

def longestCommonPrefix(strs: List[str]) -> str:
    first = strs[0]
    for i, c in enumerate(first):
        for s in strs[1:]:
            if i == len(s) or s[i] != c:
                return first[:i]
    return first

C++

string longestCommonPrefix(vector<string>& strs) {
    const string& first = strs[0];
    for (size_t i = 0; i < first.size(); i++) {
        for (size_t k = 1; k < strs.size(); k++) {
            if (i == strs[k].size() || strs[k][i] != first[i]) {
                return first.substr(0, i);
            }
        }
    }
    return first;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No common prefix First letters already differ.	`strs = [dog, racecar, car]`	`""`
One string It's its own prefix.	`strs = [alone]`	`"alone"`
Contains an empty string The empty string ends the scan immediately.	`strs = [abc, ""]`	`""`
One is a prefix of another The shorter string runs out.	`strs = [ab, abc]`	`"ab"`