π Problem Details
- Title:
14. Longest Common Prefix
- Link: https://leetcode.com/problems/longest-common-prefix/
- Difficulty: Easy
- Tags/Categories: Trie Strings
input array
strs
write a function to find the longest common prefix amongst an array of strings return""
is there isnβt one
πWhat Were My Initial Thoughts?
- we can build a trie from each of these words in the array
- inserting the first word the lognest common prefix would be the entire word since it can only compare against itself
- the next word thats inserted would make the longest common prefix up until a child node doesnt already exist
π‘ Explanation of Solution
- build the trie
- insert all words into the trie
- each node represents a character and tracks child nodes
- find the longest common prefix
- start at the root and traverse down as long as there is exactly 1 child
- if a node has more than one child, stop because the prefix diverges
- if a node represents end of a word, stop because prefixes cant exceed the lenght of the smallest string in our input array
β Complexity Analysis
Time Complexity: O(N * M)
- N = Number of words
- M = Average length of words
- We insert all words into the Trie (O(N * M)) and traverse once (O(M)).
Space Complexity: O(N * M)
- Trie stores all characters in the words.
π» Implementation of Solution
class TrieNode {
public:
TrieNode* children[26]; // Supports only lowercase English letters
bool isEndOfWord;
TrieNode() {
isEndOfWord = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEndOfWord = true;
}
string longestCommonPrefix() {
string prefix = "";
TrieNode* node = root;
while (true) {
int childCount = 0;
int nextIndex = -1;
// Count number of children and find the only available child
for (int i = 0; i < 26; i++) {
if (node->children[i]) {
childCount++;
nextIndex = i;
}
}
// Stop if there is more than one child (divergence) or we reach an end of a word
if (childCount != 1 || node->isEndOfWord) {
break;
}
// Continue to the next child in the common path
prefix += (char)(nextIndex + 'a');
node = node->children[nextIndex];
}
return prefix;
}
};
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
Trie trie;
for (const string& word : strs) {
trie.insert(word);
}
return trie.longestCommonPrefix();
}
};