14. Longest Common Prefix

📝 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();
    }
};