14. Longest Common Prefix - Explanation

Description

You are given an array of strings strs. Return the longest common prefix of all the strings.

If there is no longest common prefix, return an empty string "".

Example 1:

Input: strs = ["bat","bag","bank","band"]

Output: "ba"

Example 2:

Input: strs = ["dance","dag","danger","damage"]

Output: "da"

Example 3:

Input: strs = ["neet","feet"]

Output: ""

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] is made up of lowercase English letters if it is non-empty.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Horizontal Scanning

Intuition

Start with the first string as the initial prefix candidate. Then compare it with each subsequent string, shrinking the prefix to match only the common portion. After processing all strings, what remains is the longest common prefix. The prefix can only shrink or stay the same as we go through more strings.

Algorithm

Initialize prefix as the first string in the array.
For each subsequent string, compare characters one by one with the current prefix.
Find the index j where characters stop matching (or we run out of characters in either string).
Truncate prefix to include only characters from index 0 to j-1.
After processing all strings, return the remaining prefix.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = strs[0]
        for i in range(1, len(strs)):
            j = 0
            while j < min(len(prefix), len(strs[i])):
                if prefix[j] != strs[i][j]:
                    break
                j += 1
            prefix = prefix[:j]
        return prefix

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(1)$

Where $n$ is the length of the shortest string and $m$ is the number of strings.

2. Vertical Scanning

Intuition

Instead of comparing entire strings horizontally, we can compare characters column by column across all strings. Check if all strings have the same character at position 0, then position 1, and so on. The moment we find a mismatch or reach the end of any string, we've found where the common prefix ends.

Algorithm

Iterate through character positions starting from index 0.
At each position i, check the character in the first string.
Compare this character against position i in every other string.
If any string is too short or has a different character, return the prefix up to index i-1.
If we complete the loop without returning, the entire first string is the common prefix.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        for i in range(len(strs[0])):
            for s in strs:
                if i == len(s) or s[i] != strs[0][i]:
                    return s[:i]
        return strs[0]

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(1)$ since we did not use extra space.

Where $n$ is the length of the shortest string and $m$ is the number of strings.

3. Sorting

Intuition

When strings are sorted lexicographically, the first and last strings in the sorted order are the most different from each other. If these two extremes share a common prefix, then all strings in between must also share that same prefix. So we only need to compare the first and last strings after sorting.

Algorithm

If there's only one string, return it directly.
Sort the array of strings lexicographically.
Compare only the first and last strings in the sorted array.
Find the longest prefix they share by comparing characters one by one.
Return this prefix, which is guaranteed to be common to all strings.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]

        strs = sorted(strs)
        for i in range(min(len(strs[0]), len(strs[-1]))):
            if strs[0][i] != strs[-1][i]:
                return strs[0][:i]
        return strs[0]

Time & Space Complexity

Time complexity: $O(n * m \log m)$
Space complexity: $O(1)$ or $O(m)$ depending on the sorting algorithm.

Where $n$ is the length of the longest string and $m$ is the number of strings.

4. Trie

Intuition

A Trie naturally represents all prefixes. We insert the shortest string into the trie, then query each other string against it. For each string, we walk down the trie as far as characters match, tracking how deep we get. The minimum depth reached across all strings is the length of the longest common prefix.

Algorithm

Find the shortest string and insert it into a Trie (this limits the trie size and ensures we don't go beyond what could be common).
Initialize prefixLen to the length of the shortest string.
For each string, traverse the trie while characters match, updating prefixLen to be the minimum of its current value and how far we matched.
After checking all strings, extract the first prefixLen characters from any string as the result.

class TrieNode:
    def __init__(self):
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]

    def lcp(self, word: str, prefixLen: int) -> int:
        node = self.root
        for i in range(min(len(word), prefixLen)):
            if word[i] not in node.children:
                return i
            node = node.children[word[i]]
        return min(len(word), prefixLen)

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        if len(strs) == 1:
            return strs[0]

        mini = 0
        for i in range(1, len(strs)):
            if len(strs[mini]) > len(strs[i]):
                mini = i

        trie = Trie()
        trie.insert(strs[mini])
        prefixLen = len(strs[mini])
        for i in range(len(strs)):
            prefixLen = trie.lcp(strs[i], prefixLen)
        return strs[0][:prefixLen]

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the length of the shortest string and $m$ is the number of strings.

Common Pitfalls

Not Handling Empty Strings in the Array

If any string in the input array is empty, the longest common prefix must be an empty string. Failing to check for this case before accessing characters can lead to index out of bounds errors.

Accessing Characters Beyond String Length

When comparing characters at a given index, you must ensure the index is valid for all strings being compared. A common mistake is to iterate based on one string's length without checking if shorter strings have characters at that position.