Design Add And Search Words Data Structure Leetcode Problem 211 [Python]

Designing a data structure that can efficiently add words and search for them is a common problem in computer science and coding interviews, welcome to Design Add And Search Words Data Structure.

In this blog post, we’ll tackle the Design Add And Search Words Data Structure problem, also known as LeetCode Problem 211, categorized under Tries.

We’ll provide a Python solution that efficiently handles adding new words and searching for words, including support for wildcard characters.

Let’s dive in!

Problem Overview

The problem can be summarized as follows: design a data structure that supports adding new words and finding if a given string matches any previously added string.

The data structure should be able to handle words containing lowercase English letters and wildcard characters represented by dots (‘.’).

These dots can match any lowercase English letter.

The problem provides two main operations:

WordDictionary(): Initializes the object.
addWord(word): Adds a word to the data structure.
search(word): Returns true if there is any string in the data structure that matches the given word or false otherwise.

Here’s an example of how these operations should work:

wordDictionary = WordDictionary()
wordDictionary.addWord("bad")
wordDictionary.addWord("dad")
wordDictionary.addWord("mad")
wordDictionary.search("pad")  # Returns False
wordDictionary.search("bad")  # Returns True
wordDictionary.search(".ad")  # Returns True
wordDictionary.search("b..")  # Returns True

Constraints:

The length of a word is between 1 and 25 characters.
Words in addWord consist of lowercase English letters.
Words in search consist of lowercase English letters and dots.
There will be at most 104 calls to addWord and search.

Now, let’s explore the Python solution to this problem.

Efficient Python Code Solution

We can efficiently solve this problem using a Trie data structure.

A Trie is a tree-like data structure that stores a dynamic set of strings, where each node represents a character in the string.

Here’s a Python implementation of the solution:

View on GitHub ➹

class TrieNode:
    def __init__(self):
        self.children = {}  # Mapping from character to TrieNode
        self.word = False   # Indicates the end of a word

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

    def addWord(self, word: str) -&gt; None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.word = True

    def search(self, word: str) -&gt; bool:
        def dfs(j, root):
            cur = root

            for i in range(j, len(word)):
                c = word[i]
                if c == ".":
                    for child in cur.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                else:
                    if c not in cur.children:
                        return False
                    cur = cur.children[c]
            return cur.word

        return dfs(0, self.root)

This Python solution defines a TrieNode class for our Trie and a WordDictionary class for handling the addWord and search operations efficiently.

1. TrieNode Class

TrieNode has two attributes:
- children: A dictionary that maps characters to their corresponding child TrieNode objects.
- word: A Boolean flag to indicate the end of a word.

It’s set to True if the node marks the end of a word.

2. WordDictionary Class

WordDictionary initializes with a root node that represents the start of our Trie.
The addWord method adds a word to the Trie by iterating through the characters of the word and creating new TrieNode objects as needed.

It marks the last node as the end of the word.

The search method is the core of this problem.

It uses a depth-first search (DFS) function, dfs, to navigate the Trie based on the characters in the search word.
– If the character is not a dot (‘.’), it checks if the character exists in the current node’s children.

If not, it returns False.

Otherwise, it moves to the corresponding child node.
– If the character is a dot (‘.’), it explores all possible child nodes, recursively searching for the remaining characters.
– If it finds a matching word, it returns True.

The search method starts the DFS with the root node and the first character of the search word.

Time and Space Complexity

Now, let’s analyze the time and space complexity of our Python solution.

Time Complexity:
- addWord: Adding a word to the Trie has a time complexity of O(L), where L is the length of the word.
- search: The worst-case time complexity for searching is O(26^L), where L is the length of the search word.

However, in practice, it is often much faster than this worst-case scenario due to early stopping when a match is found.

Space Complexity:
- The space complexity depends on the number of words and the average word length.

In the worst case, where there are many unique words, the space complexity can be O(N*L), where N is the number of words and L is the average word length.

The Trie-based solution provides an efficient way to add words and search for them, even when wildcard characters are involved.

Reasoning Behind Our Approach

The core of our approach relies on the Trie data structure, which is a natural fit for this problem.

Tries are widely used for efficient string-related operations, making them suitable for tasks like adding and searching for words.

The Trie allows us to efficiently handle both regular characters and wildcard characters represented by dots (‘.’).

When adding words, we traverse the Trie, creating nodes as needed to represent each character in the word.

This ensures that we have a structured representation of all the words in the data structure.

For searching, we use a depth-first search (DFS) function that explores the Trie based on the characters in the search word.

This allows us to efficiently handle wildcard characters and early exit the search when a match is found.

In summary, our approach combines the power of the Trie data structure with recursive depth-first search to provide an elegant and efficient solution to the problem.

Conclusion

Designing a data structure that supports adding and searching for words efficiently is a common problem in computer science and coding interviews.

In this blog post, we tackled the Design Add And Search Words Data Structure problem (LeetCode Problem 211) using a Trie-based solution in Python.

We demonstrated how to efficiently handle regular characters and wildcard characters represented by dots (‘.’) in the search process.

We hope this solution has been helpful for understanding Trie data structures and how they can be applied to solve real-world problems efficiently.

If you have any questions or suggestions, please feel free to comment and share your thoughts.

This problem is a valuable addition to your coding arsenal, and mastering it will undoubtedly improve your problem-solving skills.

For more practice and to explore the problem further, you can visit the LeetCode Problem 211 page and test your implementation.

Happy coding!

Design Add And Search Words Data Structure Leetcode Problem 211 [Python]

Problem Overview

Efficient Python Code Solution

1. TrieNode Class

2. WordDictionary Class

Time and Space Complexity

Reasoning Behind Our Approach

Related Interview Questions By Company:

Related Interview Questions By Difficulty:

Related Interview Questions By Category:

Conclusion

Written By

CID

Tags