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:
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
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)
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))
['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:
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
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)
words = ["w","wo","wor","worl","world"] print(longestWord(words))
"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.