Facebook Pixel

676. Implement Magic Dictionary

MediumDepth-First SearchDesignTrieHash TableString
Leetcode Link

Problem Description

You need to design a data structure called MagicDictionary that can determine if a given string can be transformed into any word in a pre-loaded dictionary by changing exactly one character.

The data structure should support the following operations:

  1. MagicDictionary(): Initializes an empty MagicDictionary object.

  2. buildDict(dictionary): Takes an array of distinct strings and stores them in the data structure. This sets up your dictionary of valid words.

  3. search(searchWord): Takes a string and returns true if you can change exactly one character in searchWord to match any word stored in the dictionary. Returns false otherwise.

Important constraints:

  • You must change exactly one character - no more, no less
  • The change must result in a word that exists in the dictionary
  • All words in the dictionary are distinct

For example, if your dictionary contains ["hello", "hallo"] and you search for "hello", the result would be true because you can change the 'e' to 'a' to get "hallo" which is in the dictionary. However, if you search for "hallo", it would also return true because you can change the 'a' to 'e' to get "hello".

The solution uses a Trie data structure combined with depth-first search (DFS) to efficiently check all possible single-character modifications. During the search, it tracks whether exactly one character has been changed and validates that the resulting word exists in the dictionary.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The Trie data structure used in this problem is essentially a tree (which is a special type of graph). Each node represents a character, and edges connect characters to form words. The dictionary words are stored as paths from root to leaf nodes.

Is it a tree?

  • Yes: A Trie is specifically a tree data structure. It has a single root node, and each node can have multiple children (one for each possible character), with no cycles.

DFS

  • Yes: Since we're working with a tree structure and need to explore paths from root to leaf while tracking modifications, DFS is the appropriate choice.

Conclusion: The flowchart leads us directly to using DFS for this problem.

Why DFS is Perfect for This Problem

The DFS approach works particularly well here because:

  1. Path Exploration: We need to traverse from the root of the Trie to a leaf node, checking each character along the way. DFS naturally follows paths from start to end.

  2. Backtracking Capability: When we encounter a mismatch, we need to either:

    • Use our one allowed modification and continue down that path
    • Try different branches (different character substitutions)

    DFS with backtracking handles this elegantly.

  3. State Tracking: During traversal, we need to track whether we've used our one allowed character change. The recursive nature of DFS makes it easy to pass this state (diff parameter) through the traversal.

  4. Early Termination: DFS allows us to stop exploring a path as soon as we know it won't lead to a valid solution (e.g., when we've already used our one modification and encounter another mismatch).

The search process explores the Trie depth-first, maintaining the count of character differences, and returns true only when exactly one character has been modified and we've reached a valid word ending.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

When we need to check if we can transform a word by changing exactly one character, the naive approach would be to generate all possible single-character modifications and check if any exist in our dictionary. However, this would be inefficient, especially with repeated searches.

The key insight is that we can leverage the structure of a Trie to guide our search more intelligently. Instead of generating all modifications upfront, we can explore the Trie path-by-path and make decisions at each character position.

Think of it like walking through a maze where you have one "magic pass" that lets you walk through exactly one wall. As you traverse each path in the Trie:

  1. When characters match: Continue following the current path without using your magic pass
  2. When characters don't match: You have two choices:
    • If you haven't used your magic pass yet, use it now to pretend this character matches and continue
    • Try other branches at this position (effectively trying different character substitutions)

The beauty of this approach is that we're not blindly trying all possible modifications. Instead, we're letting the Trie structure guide us to only explore modifications that could potentially lead to valid words in our dictionary.

The recursive DFS naturally handles the backtracking needed when a path doesn't work out. If we reach the end of a word in the Trie and we've used our magic pass exactly once, we've found a valid match. If we've used it zero times (perfect match) or more than once (too many differences), it's not what we're looking for.

This approach elegantly combines the efficiency of Trie lookups with the flexibility of DFS exploration, allowing us to check all possible single-character modifications without explicitly generating them.

Learn more about Depth-First Search and Trie patterns.

Solution Approach

The solution uses a Trie data structure combined with DFS to efficiently handle the search for words with exactly one character difference. Let's walk through the implementation:

Building the Trie Structure

The [Trie](/problems/trie_intro) class has two main components:

  • children: A dictionary mapping characters to child Trie nodes
  • is_end: A boolean flag marking the end of a valid word

The insert method adds words to the Trie by creating a path from root to leaf, with each node representing a character. When we reach the end of a word, we mark is_end = True.

The DFS Search Strategy

The core logic lies in the search method, which uses a nested DFS function with three parameters:

  • i: Current position in the search word
  • node: Current node in the Trie
  • diff: Number of character differences encountered so far (0 or 1)

The DFS explores two scenarios at each character position:

  1. Exact Match Path: If w[i] exists in node.children, we can follow this path without using our modification:

    if w[i] in node.children and dfs(i + 1, node.children[w[i]], diff):
        return True
  2. Modification Path: If we haven't used our modification yet (diff == 0), we can try changing the current character to any other available character in the Trie:

    return diff == 0 and any(
        dfs(i + 1, node.children[c], 1) for c in node.children if c != w[i]
    )

    This tries all possible character substitutions at the current position, marking diff = 1 to indicate we've used our one allowed change.

Base Case and Validation

When we reach the end of the search word (i == len(w)), we check two conditions:

  • diff == 1: We must have changed exactly one character
  • node.is_end: We must be at a valid word ending in the Trie

Both conditions must be true for a successful match.

MagicDictionary Wrapper

The MagicDictionary class simply wraps the Trie functionality:

  • buildDict: Inserts all dictionary words into the Trie
  • search: Delegates to the Trie's search method

This approach has a time complexity of O(n * m) for building the dictionary (where n is the number of words and m is the average word length) and O(m * 26) for searching (where we might explore up to 26 different character branches at each position).

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Setup: Build a dictionary with words ["hello", "hallo", "leetc"]

The Trie structure after building looks like this:

        root
       /    \
      h      l
      |      |
      e,a    e
      |      |
      l      e
      |      |
      l      t
      |      |
      o*     c*

(* marks end of word)

Search 1: Search for "hello" (should return true)

Starting DFS with i=0, node=root, diff=0:

  1. At position 0 ('h'):

    • Found 'h' in children, follow exact match path
    • Continue with i=1, node=h_node, diff=0
  2. At position 1 ('e'):

    • Found 'e' in children, follow exact match path
    • Continue with i=2, node=e_node, diff=0
  3. At position 2 ('l'):

    • Found 'l' in children, follow exact match path
    • Continue with i=3, node=l_node, diff=0
  4. At position 3 ('l'):

    • Found 'l' in children, follow exact match path
    • Continue with i=4, node=l_node, diff=0
  5. At position 4 ('o'):

    • Found 'o' in children, follow exact match path
    • Continue with i=5, node=o_node, diff=0
  6. Reached end (i=5):

    • Check: diff == 1? No (diff=0) โ†’ return false
    • Backtrack to position 1
  7. Back at position 1 ('e'), try modification path:

    • Since diff=0, we can try changing 'e' to 'a'
    • Continue with i=2, node=a_node, diff=1
  8. Continue down the 'a' branch with remaining "llo":

    • All characters match in the Trie
    • Reach end with diff=1 and is_end=True
    • Return true!

Search 2: Search for "leetd" (should return true)

Starting DFS with i=0, node=root, diff=0:

  1. Follow exact matches for "leet" (positions 0-3)
  2. At position 4 ('d'):
    • 'd' not in children at this node
    • Since diff=0, try modification to 'c' (available in Trie)
    • Continue with i=5, node=c_node, diff=1
  3. Reached end with diff=1 and is_end=True โ†’ return true

Search 3: Search for "hxllo" (should return false)

  1. At position 0 ('h'): Follow 'h' path
  2. At position 1 ('x'):
    • 'x' not in children
    • Try modifications to 'e' or 'a' with diff=1
  3. Following 'e' path with "llo" โ†’ reaches valid word
  4. But we changed 'x'โ†’'e', making "hello" which exists!
  5. Return true

Wait, let me reconsider Search 3...

Search 3 (corrected): Search for "world" (should return false)

  1. At position 0 ('w'):
    • 'w' not in children of root
    • Since diff=0, try modifications to 'h' or 'l'
  2. If we change to 'h', we'd need "orld" to match remaining path
    • But Trie only has "ello" or "allo" after 'h'
    • No match possible
  3. If we change to 'l', we'd need "orld" to match remaining path
    • But Trie only has "eetc" after 'l'
    • No match possible
  4. All paths exhausted โ†’ return false

This example demonstrates how the DFS explores both exact match paths and modification paths, backtracking when needed, and only returns true when exactly one character difference leads to a valid dictionary word.

Solution Implementation

1from typing import List, Dict, Optional
2
3
4class Trie:
5    """Trie (prefix tree) data structure with support for fuzzy search."""
6  
7    __slots__ = ["children", "is_end"]
8  
9    def __init__(self) -> None:
10        """Initialize an empty trie node."""
11        self.children: Dict[str, 'Trie'] = {}
12        self.is_end: bool = False
13  
14    def insert(self, word: str) -> None:
15        """
16        Insert a word into the trie.
17      
18        Args:
19            word: The word to insert into the trie
20        """
21        current_node = self
22        for char in word:
23            if char not in current_node.children:
24                current_node.children[char] = Trie()
25            current_node = current_node.children[char]
26        current_node.is_end = True
27  
28    def search(self, word: str) -> bool:
29        """
30        Search for a word that differs by exactly one character.
31      
32        Args:
33            word: The word to search for (with one character difference)
34          
35        Returns:
36            True if a word exists that differs by exactly one character, False otherwise
37        """
38        def dfs(index: int, node: 'Trie', difference_count: int) -> bool:
39            """
40            Depth-first search to find a word with exactly one character difference.
41          
42            Args:
43                index: Current position in the search word
44                node: Current trie node
45                difference_count: Number of character differences found so far
46              
47            Returns:
48                True if a valid word with exactly one difference is found
49            """
50            # Base case: reached end of search word
51            if index == len(word):
52                return difference_count == 1 and node.is_end
53          
54            # Try to continue with the same character (no difference)
55            if word[index] in node.children and dfs(index + 1, node.children[word[index]], difference_count):
56                return True
57          
58            # Try to use a different character (add one difference)
59            # Only allowed if we haven't used our one difference yet
60            return difference_count == 0 and any(
61                dfs(index + 1, node.children[char], 1) 
62                for char in node.children 
63                if char != word[index]
64            )
65      
66        return dfs(0, self, 0)
67
68
69class MagicDictionary:
70    """
71    A dictionary that supports searching for words with exactly one character modification.
72    """
73  
74    def __init__(self) -> None:
75        """Initialize an empty MagicDictionary."""
76        self.trie = Trie()
77  
78    def buildDict(self, dictionary: List[str]) -> None:
79        """
80        Build the dictionary from a list of words.
81      
82        Args:
83            dictionary: List of words to add to the dictionary
84        """
85        for word in dictionary:
86            self.trie.insert(word)
87  
88    def search(self, searchWord: str) -> bool:
89        """
90        Search if there exists any word in the dictionary that differs 
91        by exactly one character from the search word.
92      
93        Args:
94            searchWord: The word to search for (with one character modification)
95          
96        Returns:
97            True if such a word exists in the dictionary, False otherwise
98        """
99        return self.trie.search(searchWord)
100
101
102# Your MagicDictionary object will be instantiated and called as such:
103# obj = MagicDictionary()
104# obj.buildDict(dictionary)
105# param_2 = obj.search(searchWord)
106
1/**
2 * Trie (Prefix Tree) implementation for efficient string storage and search
3 */
4class Trie {
5    // Array to store child nodes for each letter (a-z)
6    private Trie[] children = new Trie[26];
7    // Flag to mark if current node represents end of a word
8    private boolean isEnd;
9
10    /**
11     * Inserts a word into the trie
12     * @param word The word to insert
13     */
14    public void insert(String word) {
15        Trie currentNode = this;
16      
17        // Traverse through each character in the word
18        for (char character : word.toCharArray()) {
19            int index = character - 'a';
20          
21            // Create new node if path doesn't exist
22            if (currentNode.children[index] == null) {
23                currentNode.children[index] = new Trie();
24            }
25          
26            // Move to the child node
27            currentNode = currentNode.children[index];
28        }
29      
30        // Mark the last node as end of word
31        currentNode.isEnd = true;
32    }
33
34    /**
35     * Searches for a word with exactly one character difference
36     * @param word The word to search for
37     * @return true if a word exists with exactly one character difference
38     */
39    public boolean search(String word) {
40        return dfs(word, 0, this, 0);
41    }
42
43    /**
44     * Depth-first search to find a word with specified number of differences
45     * @param word The target word to search
46     * @param charIndex Current character index being processed
47     * @param currentNode Current trie node being explored
48     * @param diffCount Number of character differences encountered so far
49     * @return true if valid word found with exactly one difference
50     */
51    private boolean dfs(String word, int charIndex, Trie currentNode, int diffCount) {
52        // Base case: reached end of word
53        if (charIndex == word.length()) {
54            // Valid only if exactly one difference and current node is end of a word
55            return diffCount == 1 && currentNode.isEnd;
56        }
57      
58        // Get the index for current character
59        int currentCharIndex = word.charAt(charIndex) - 'a';
60      
61        // Try following the exact path (no additional difference)
62        if (currentNode.children[currentCharIndex] != null) {
63            if (dfs(word, charIndex + 1, currentNode.children[currentCharIndex], diffCount)) {
64                return true;
65            }
66        }
67      
68        // If no difference used yet, try all other possible characters (introducing one difference)
69        if (diffCount == 0) {
70            for (int alternativeIndex = 0; alternativeIndex < 26; alternativeIndex++) {
71                // Skip the original character and null children
72                if (alternativeIndex != currentCharIndex && currentNode.children[alternativeIndex] != null) {
73                    // Continue search with one difference counted
74                    if (dfs(word, charIndex + 1, currentNode.children[alternativeIndex], 1)) {
75                        return true;
76                    }
77                }
78            }
79        }
80      
81        return false;
82    }
83}
84
85/**
86 * Magic Dictionary that supports searching for words with exactly one character modification
87 */
88class MagicDictionary {
89    // Trie data structure to store dictionary words
90    private Trie trie = new Trie();
91
92    /**
93     * Constructor for MagicDictionary
94     */
95    public MagicDictionary() {
96        // Initialize with empty trie (already done in field declaration)
97    }
98
99    /**
100     * Builds the dictionary from an array of words
101     * @param dictionary Array of words to add to the dictionary
102     */
103    public void buildDict(String[] dictionary) {
104        // Insert each word into the trie
105        for (String word : dictionary) {
106            trie.insert(word);
107        }
108    }
109
110    /**
111     * Searches if there exists a word in the dictionary that differs by exactly one character
112     * @param searchWord The word to search for
113     * @return true if such a word exists in the dictionary
114     */
115    public boolean search(String searchWord) {
116        return trie.search(searchWord);
117    }
118}
119
120/**
121 * Your MagicDictionary object will be instantiated and called as such:
122 * MagicDictionary obj = new MagicDictionary();
123 * obj.buildDict(dictionary);
124 * boolean param_2 = obj.search(searchWord);
125 */
126
1class Trie {
2private:
3    Trie* children[26];  // Array of pointers to child nodes (one for each letter a-z)
4    bool isEndOfWord;    // Flag indicating if this node represents the end of a word
5  
6public:
7    // Constructor: Initialize all children pointers to nullptr
8    Trie() {
9        fill(begin(children), end(children), nullptr);
10        isEndOfWord = false;
11    }
12  
13    // Insert a word into the trie
14    void insert(const string& word) {
15        Trie* currentNode = this;
16      
17        // Traverse through each character of the word
18        for (char ch : word) {
19            int index = ch - 'a';  // Convert character to array index (0-25)
20          
21            // Create a new node if the path doesn't exist
22            if (!currentNode->children[index]) {
23                currentNode->children[index] = new Trie();
24            }
25          
26            // Move to the child node
27            currentNode = currentNode->children[index];
28        }
29      
30        // Mark the end of the word
31        currentNode->isEndOfWord = true;
32    }
33  
34    // Search for a word with exactly one character difference
35    bool search(const string& word) {
36        // Lambda function for depth-first search
37        // Parameters: current position in word, current trie node, number of differences found
38        function<bool(int, Trie*, int)> dfs = [&](int position, Trie* node, int diffCount) {
39            // Base case: reached end of the word
40            if (position >= word.size()) {
41                // Return true only if exactly one difference was found and we're at a word end
42                return diffCount == 1 && node->isEndOfWord;
43            }
44          
45            int charIndex = word[position] - 'a';
46          
47            // Try matching the exact character at current position
48            if (node->children[charIndex] && dfs(position + 1, node->children[charIndex], diffCount)) {
49                return true;
50            }
51          
52            // If no differences found yet, try all other characters (to introduce one difference)
53            if (diffCount == 0) {
54                for (int k = 0; k < 26; ++k) {
55                    // Skip the exact matching character (already tried above)
56                    if (k != charIndex && node->children[k]) {
57                        // Continue search with difference count = 1
58                        if (dfs(position + 1, node->children[k], 1)) {
59                            return true;
60                        }
61                    }
62                }
63            }
64          
65            return false;
66        };
67      
68        // Start DFS from root with 0 differences
69        return dfs(0, this, 0);
70    }
71};
72
73class MagicDictionary {
74private:
75    Trie* trie;  // Pointer to the trie data structure
76  
77public:
78    // Constructor: Initialize the trie
79    MagicDictionary() {
80        trie = new Trie();
81    }
82  
83    // Build the dictionary by inserting all words into the trie
84    void buildDict(vector<string> dictionary) {
85        for (auto& word : dictionary) {
86            trie->insert(word);
87        }
88    }
89  
90    // Search for a word that differs by exactly one character from searchWord
91    bool search(string searchWord) {
92        return trie->search(searchWord);
93    }
94};
95
96/**
97 * Your MagicDictionary object will be instantiated and called as such:
98 * MagicDictionary* obj = new MagicDictionary();
99 * obj->buildDict(dictionary);
100 * bool param_2 = obj->search(searchWord);
101 */
102
1// Trie node structure for storing dictionary words
2interface TrieNode {
3    children: (TrieNode | null)[];
4    isEndOfWord: boolean;
5}
6
7// Global trie root
8let trieRoot: TrieNode | null = null;
9
10/**
11 * Creates a new Trie node
12 */
13function createTrieNode(): TrieNode {
14    return {
15        children: Array(26).fill(null),
16        isEndOfWord: false
17    };
18}
19
20/**
21 * Inserts a word into the Trie
22 */
23function insertWord(word: string): void {
24    if (!trieRoot) {
25        trieRoot = createTrieNode();
26    }
27  
28    let currentNode: TrieNode = trieRoot;
29  
30    for (const char of word) {
31        const index: number = char.charCodeAt(0) - 'a'.charCodeAt(0);
32      
33        if (!currentNode.children[index]) {
34            currentNode.children[index] = createTrieNode();
35        }
36      
37        currentNode = currentNode.children[index]!;
38    }
39  
40    currentNode.isEndOfWord = true;
41}
42
43/**
44 * Searches for a word with exactly one character difference
45 */
46function searchWithOneDiff(word: string): boolean {
47    if (!trieRoot) {
48        return false;
49    }
50  
51    /**
52     * DFS helper function to traverse the Trie
53     * @param charIndex - Current character index in the word
54     * @param node - Current Trie node
55     * @param diffCount - Number of character differences found so far
56     */
57    const depthFirstSearch = (charIndex: number, node: TrieNode, diffCount: number): boolean => {
58        // Base case: reached end of word
59        if (charIndex >= word.length) {
60            return diffCount === 1 && node.isEndOfWord;
61        }
62      
63        const targetCharIndex: number = word.charCodeAt(charIndex) - 'a'.charCodeAt(0);
64      
65        // Try exact match path
66        if (node.children[targetCharIndex] && 
67            depthFirstSearch(charIndex + 1, node.children[targetCharIndex]!, diffCount)) {
68            return true;
69        }
70      
71        // Try different character paths (only if no difference has been used yet)
72        if (diffCount === 0) {
73            for (let alphabetIndex = 0; alphabetIndex < 26; alphabetIndex++) {
74                // Skip the exact match character
75                if (alphabetIndex !== targetCharIndex && 
76                    node.children[alphabetIndex] && 
77                    depthFirstSearch(charIndex + 1, node.children[alphabetIndex]!, 1)) {
78                    return true;
79                }
80            }
81        }
82      
83        return false;
84    };
85  
86    return depthFirstSearch(0, trieRoot, 0);
87}
88
89/**
90 * Builds a dictionary from an array of words
91 */
92function buildDict(dictionary: string[]): void {
93    // Reset the trie
94    trieRoot = null;
95  
96    // Insert all words into the trie
97    for (const word of dictionary) {
98        insertWord(word);
99    }
100}
101
102/**
103 * Searches if a word exists in the dictionary with exactly one character modified
104 */
105function search(searchWord: string): boolean {
106    return searchWithOneDiff(searchWord);
107}
108

Time and Space Complexity

Time Complexity:

  • buildDict: Building the trie requires iterating through each word in the dictionary and inserting each character. For n words with average length l, this takes O(n ร— l) time.
  • search: For each search operation, we perform a DFS traversal. In the worst case:
    • We traverse through all l characters of the search word
    • At each position, when diff = 0 (no difference used yet), we potentially explore all children except the matching character
    • This means checking up to |ฮฃ| - 1 alternative branches (where |ฮฃ| = 26 for lowercase letters)
    • Each branch continues the DFS for the remaining characters
    • This gives us O(l ร— |ฮฃ|) time per search operation

Overall time complexity: O(n ร— l + q ร— l ร— |ฮฃ|) where:

  • n = number of words in dictionary
  • l = average length of words
  • q = number of search operations
  • |ฮฃ| = size of character set (26 for lowercase English letters)

Space Complexity:

  • The trie stores all words from the dictionary
  • In the worst case, if all words are completely different, we need O(n ร— l) nodes
  • The recursive DFS call stack can go up to depth l during search, adding O(l) space
  • Since O(n ร— l) > O(l) for any reasonable dictionary, the dominant factor is the trie storage

Overall space complexity: O(n ร— l) where:

  • n = number of words in dictionary
  • l = average length of words

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Check Exact Match Without Modification

A critical pitfall is incorrectly handling the case where the search word exactly matches a dictionary word. The problem requires exactly one character change, so an exact match should return false.

Incorrect Implementation:

def dfs(index: int, node: 'Trie', difference_count: int) -> bool:
    if index == len(word):
        return node.is_end  # Wrong! Doesn't check if we made exactly one change

Correct Implementation:

def dfs(index: int, node: 'Trie', difference_count: int) -> bool:
    if index == len(word):
        return difference_count == 1 and node.is_end  # Must have exactly 1 difference

2. Inefficient Character Difference Exploration

Another common mistake is exploring all 26 possible characters when trying modifications, even when most don't exist in the trie. This leads to unnecessary recursion and performance degradation.

Inefficient Approach:

# Trying all 26 letters regardless of what's in the trie
if difference_count == 0:
    for c in 'abcdefghijklmnopqrstuvwxyz':
        if c != word[index] and c in node.children:
            if dfs(index + 1, node.children[c], 1):
                return True

Efficient Approach (as in the solution):

# Only iterate through characters that actually exist in the trie
return difference_count == 0 and any(
    dfs(index + 1, node.children[char], 1) 
    for char in node.children 
    if char != word[index]
)

3. Incorrect Difference Count Management

A subtle bug can occur when the difference count is incremented incorrectly or when allowing multiple changes.

Wrong Pattern:

def dfs(index: int, node: 'Trie', difference_count: int) -> bool:
    # ... base case ...
  
    # Bug: This allows unlimited changes
    for char in node.children:
        if dfs(index + 1, node.children[char], difference_count + (char != word[index])):
            return True
    return False

This implementation would incorrectly allow multiple character changes because it doesn't restrict exploration once a change has been made.

Correct Pattern: The solution correctly separates the logic:

  • First, try the exact match path (no change)
  • Then, only if no change has been made yet (difference_count == 0), try modification paths

4. Memory Inefficiency with Redundant Trie Nodes

While not a correctness issue, creating unnecessary Trie nodes for empty paths can waste memory. Always ensure nodes are created only when needed:

Wasteful:

def insert(self, word: str) -> None:
    current_node = self
    for char in word:
        current_node.children[char] = current_node.children.get(char, Trie())
        current_node = current_node.children[char]
    current_node.is_end = True

Memory-Efficient (as in the solution):

def insert(self, word: str) -> None:
    current_node = self
    for char in word:
        if char not in current_node.children:
            current_node.children[char] = Trie()
        current_node = current_node.children[char]
    current_node.is_end = True
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?


Recommended Readings

Want a Structured Path to Master System Design Too? Donโ€™t Miss This!

Load More