Longest Common Prefix
Easy · Arrays & Hashing · Explanation and code example
Trie
How it works
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.
Steps
- 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
prefixLento the length of the shortest string. - For each string, traverse the trie while characters match, updating
prefixLento be the minimum of its current value and how far we matched. - After checking all strings, extract the first
prefixLencharacters from any string as the result.
Complexity
- Time complexity:
O(n * m) - Space complexity:
O(n)
Where
nis the length of the shortest string andmis the number of strings.
Things to watch for
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.
Python code example
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]
C++ code example
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
}
int lcp(const string& word, int prefixLen) {
TrieNode* node = root;
int i = 0;
while (i < min((int)word.length(), prefixLen)) {
if (node->children.find(word[i]) == node->children.end()) {
return i;
}
node = node->children[word[i]];
i++;
}
return min((int)word.length(), prefixLen);
}
};
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 1) {
return strs[0];
}
int mini = 0;
for (int i = 1; i < strs.size(); i++) {
if (strs[mini].size() > strs[i].size()) {
mini = i;
}
}
Trie trie;
trie.insert(strs[mini]);
int prefixLen = strs[mini].length();
for (int i = 0; i < strs.size(); i++) {
prefixLen = trie.lcp(strs[i], prefixLen);
}
return strs[0].substr(0, prefixLen);
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.