Word Search II using Trie 🎯

Welcome to our comprehensive guide on Word Search II using Trie! This lesson is designed to help you understand the concept from the ground up, making it suitable for both beginners and intermediates. Let's dive in!

What is a Trie? 💡

A Trie, also known as a prefix tree or digital tree, is a tree data structure used to efficiently store and retrieve keys in a dataset. Each node in a Trie represents a character, and branches represent the subsequent characters that can follow.

Why use a Trie? 📝

Tries are particularly useful when we have a large dataset of strings and need to perform operations like searching for a string, inserting a string, or finding all strings with a certain prefix efficiently.

Building a Trie 💡

Let's build a simple Trie in Python to store words for a word search.

python

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

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

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

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Now that we have our Trie, let's use it to perform a word search!

Word Search with a Trie 💡

Given a list of words and a sentence, our goal is to find all occurrences of the words in the sentence.

Here's how we can do it:

Build a Trie from the list of words.
Iterate through each word in the Trie, starting from the root node.
Traverse the Trie, following the character branches that match the sentence.
If we reach a node that represents the end of a word, we've found a match!

python

sentence = "the quick brown fox jumps over the lazy dog"
words = ["the", "quick", "brown", "fox", "jumps", "over", "dog", "lazy"]

trie = Trie()
for word in words:
    trie.insert(word)

matches = []
node = trie.root
for word in sentence.split():
    for char in word:
        if char not in node.children:
            break
        node = node.children[char]
        if node.end_of_word:
            matches.append(word)
            node = trie.root

print(matches)  # Output: ['the', 'quick', 'brown', 'fox', 'lazy']

Quiz 📝

That's it for our lesson on Word Search II using Trie! We hope this tutorial has been helpful in understanding the concept and building practical applications. Happy coding! 💡🚀