< Back





1268. Search Suggestions System

We're working with tries, also a tree but the nodes in the data structure are contsructed
differently and for a different purpose. In a trie, the root node is "", an empty string. All its
children are the first character of a word, and the children of those characters are the succeeding
character of word.

This data structure maintains words in tree format, and the leaf will allow us to construct the full
word. This allows us to be able to easily search and lookup words from our original data set, by
following the tree for the characters we're looking for.

In this particular problem, we're asked to provide search suggestions based on the characters typed
in the input. For each character, we need to provide a list of 3 words (maximum) that start with the
prefix written by the user.

We construct a trie, and we assign a suggestions attribute to each node, containing a
lexicographically sorted list of words with a maximum size of 3. These words have a prefix matching
the current node's path and depth.

Then, for each character in the search word, we traverse the tree and append the suggestions to our
answer array, if the character matches our current node. If the character doesn't match our current
node, we know that the user is typing a word that isn't in our list of products, so we clear out our
children nodes from the current node and append an empty suggestion list to our answer.

The solution is as follows:


  class TrieNode:
      def __init__(self):
          self.children = {}
          self.suggestions = []

  class Solution:
      def buildTrie(self, words: List[str]) -> TrieNode:
          root = TrieNode()

          for word in words:
              curr = root

              for char in word:
                  if char not in curr.children:
                      curr.children[char] = TrieNode()

                  curr = curr.children[char]
                  curr.suggestions.append(word)
                  curr.suggestions.sort()

                  if len(curr.suggestions) > 3:
                      curr.suggestions.pop()

          return root

      def suggestedProducts(
          self, products: List[str], searchWord: str
      ) -> List[List[str]]:
          node, ans = self.buildTrie(products), []

          for char in searchWord:
              if char in node.children:
                  node = node.children[char]
                  ans.append(node.suggestions)
              else:
                  node.children = {}
                  ans.append([])

          return ans


_ Time Complexity:

  O(m * n) - We search the entire grid for rotten and fresh oranges.

_ Space Complexity:

  O(m * n) - We could store all oranges in a set of size m * n in the worst case.