Certainly! Trie, also known as a prefix tree, is a versatile data structure commonly used in string-related problems. It efficiently stores and retrieves strings, making it useful in various scenarios. Let's explore how to use the Trie data structure with example questions and solutions.

Example Question 1: Word Search II

Given a 2D board of characters and a list of words, find all words on the board. Each word must be constructed from adjacent cells (horizontal or vertical) on the board. You may reuse letters of the same cell to form a word.

Example:

Board:
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Words: ["oath","pea","eat","rain"]

Solution: To efficiently solve this problem, we can build a Trie using the given list of words. Then, we perform a depth-first search (DFS) on the board, checking if the current sequence of letters forms a valid word in the Trie.

Here's a step-by-step implementation:

1. Construct the Trie:
   
    

   class TrieNode:
       def __init__(self):
           self.children = {}
           self.word = None
   
   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.word = word
   
       def search(self, word):
           node = self.root
           for char in word:
               if char not in node.children:
                   return None
               node = node.children[char]
           return node.word
   

   
   
   
2. Define the main function to find words on the board:
   

   def findWords(board, words):
       if not board or not board[0] or not words:
           return []
   
       trie = Trie()
       for word in words:
           trie.insert(word)
   
       m, n = len(board), len(board[0])
       result = set()
   
       def dfs(i, j, node):
           if node.word:
               result.add(node.word)
   
           if i < 0 or i >= m or j < 0 or j >= n or board[i][j] not in node.children:
               return
   
           char = board[i][j]
           board[i][j] = '#'  # Mark visited
   
           dfs(i + 1, j, node.children[char])
           dfs(i - 1, j, node.children[char])
           dfs(i, j + 1, node.children[char])
           dfs(i, j - 1, node.children[char])
   
           board[i][j] = char  # Restore the letter
   
       for i in range(m):
           for j in range(n):
               dfs(i, j, trie.root)
   
       return list(result)
   

   
   
   
3. Test the solution
   

   board = [
       ['o','a','a','n'],
       ['e','t','a','e'],
       ['i','h','k','r'],
       ['i','f','l','v']
   ]
   words = ["oath","pea","eat","rain"]
   
   print(findWords(board, words))
   

4. The output will be:

['oath', 'eat']

The solution finds all the words from the given list that can be formed by adjacent characters on the board.

Example Question 2: Longest Word in Dictionary
Given a list of strings, find the longest word that can be built one character at a time by using other words from the same list. If there are multiple possible answers, return the longest word with the smallest lexicographical order.

Example:

Input: ["w","wo","wor","worl","world"]
Output: "world"

Solution: To solve this problem, we can build a Trie using the given list of words and perform a depth-first search (DFS) on the Trie. Starting from the root node, we traverse the Trie and find the longest word that satisfies the given condition.

Here's the implementation:

1. Construct the Trie:
   

   class TrieNode:
       def __init__(self):
           self.children = {}
           self.is_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.is_word = True
   

   
   
   
2. Define the main function to find the longest word:
   

   def longestWord(words):
       trie = Trie()
       for word in words:
           trie.insert(word)
   
       def dfs(node):
           longest = ""
           for char, child in node.children.items():
               if child.is_word:
                   curr_word = char + dfs(child)
                   if len(curr_word) > len(longest) or (len(curr_word) == len(longest) and curr_word < longest):
                       longest = curr_word
           return longest
   
       return dfs(trie.root)
   

   
   
   
3. Test the solution:
   

   words = ["w","wo","wor","worl","world"]
   
   print(longestWord(words))
   

   
   
   
4. The output will be:
   

   "world"
   

   
   
   

The solution finds the longest word that can be formed one character at a time using other words from the given list.

These are two examples of how to use the Trie data structure to solve coding interview questions. Trie is particularly helpful when dealing with string-related problems that involve searching, matching, or building words efficiently.