Longest Common Prefix (Trie Approach) 🎯

Welcome to this in-depth guide on the Trie approach to find the longest common prefix in an array of strings! This lesson is designed for beginners and intermediates, so don't worry if you're just starting out. Let's dive right in! 🚀

What is Trie and Why Use it? 📝

A Trie (short for Retrieval Tree) is a tree-like data structure used to efficiently store and retrieve information from a large dataset. It's particularly useful when dealing with strings, as it allows fast searching and inserting of words, making it an ideal choice for tasks like finding the longest common prefix. 💡

Trie Nodes and Structure 📝

Each node in a Trie represents a character in a string and has the following properties:

is_end_of_word: A flag indicating whether the current node represents the end of a word.
children: A dictionary containing the nodes for each character that can follow the current character.

Building the Trie 🎯

Let's build a Trie for the following list of words:

["flower", "flow", "flight", "float", "flame"]

Here's how we'll create the Trie step-by-step:

Initialize the root node:

python

root = TrieNode()

Insert each word into the Trie:

python

def insert(word):
    current_node = root
    for char in word:
        if char not in current_node.children:
            current_node.children[char] = TrieNode()
        current_node = current_node.children[char]
    current_node.is_end_of_word = True

Finding the Longest Common Prefix 🎯

Now that we've built our Trie, let's find the longest common prefix for the given words. To do this, we'll traverse the Trie starting from the root node, and at each step, we'll move to the node with the most common character.

Here's the algorithm in pseudocode:

longest_common_prefix = ""
current_node = root

for char in first_word:
    if char not in current_node.children:
        break
    current_node = current_node.children[char]

    for word in words[1:]:
        if char not in word or current_node.children[char] is None:
            break
        current_node = current_node.children[char]

    if current_node is None:
        break

    longest_common_prefix += char

Implementation 📝

Let's implement the Trie, the insert function, and the longest_common_prefix function in Python:

python

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

def insert(root, word):
    current_node = root
    for char in word:
        if char not in current_node.children:
            current_node.children[char] = TrieNode()
        current_node = current_node.children[char]
    current_node.is_end_of_word = True

def longest_common_prefix(root, words):
    longest_common_prefix = ""
    current_node = root

    for word in words:
        for char in word:
            if char not in current_node.children:
                return longest_common_prefix
            current_node = current_node.children[char]

    while current_node is not None:
        longest_common_prefix += current_node.children.keys()[0]
        current_node = current_node.children[longest_common_prefix[-1]]

    return longest_common_prefix

# Initialize the root node
root = TrieNode()

# Insert words into the Trie
words = ["flower", "flow", "flight", "float", "flame"]
for word in words:
    insert(root, word)

# Find the longest common prefix
longest_common_prefix = longest_common_prefix(root, words)
print(longest_common_prefix)  # Output: "fl"

:::quiz
What is a Trie used for?
A: Storing and retrieving data from a large dataset
B: Performing complex calculations
C: Compressing files
Correct: A

What is a Trie node's `is_end_of_word` flag used for?
A: Indicating whether the current node represents the end of a word
B: Indicating whether the current node is a leaf node
C: Indicating whether the current node has children
Correct: A

What character does the algorithm traverse to next when it reaches a node with no children?
A: The first character in the next word
B: The first character in the previous word
C: The first character in the alphabet
Correct: A

Which of the following lines of code is responsible for inserting a word into the Trie?
A: `def longest_common_prefix(root, words):`
B: `current_node.children = {}`
C: `def insert(root, word):`
Correct: C

Which of the following functions is responsible for finding the longest common prefix?
A: `def insert(root, word):`
B: `longest_common_prefix(root, words)`
C: `def longest_common_prefix():`
Correct: B