Word Search II 30 XP Hard

LeetCode Ctrl+Enter Run Ctrl+S Save

Given a board and a list of words, find all words that can be formed on the board. Combines Trie + Backtracking — the ultimate combo.

Build a Trie from all words. DFS from each board cell, following Trie paths. When we reach is_end, we found a word. Prune branches with no Trie matches.

💡 Pro tip: Understand this problem deeply — don't just memorize the code. Try explaining the approach out loud as if teaching a friend. If you can explain it simply, you truly understand it!

📋 Instructions

Find all words from the list that exist in the board. Print count found.

Build Trie from words. For each cell, DFS while following Trie. When is_end found, add word to result.

🧪 Test Cases

Input

len(findWords(board, words))

Expected

2

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

def findWords(board, words):
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.word = w
    
    rows, cols = len(board), len(board[0])
    result = set()
    
    def dfs(r, c, node):
        if r<0 or r>=rows or c<0 or c>=cols:
            return
        ch = board[r][c]
        if ch not in node.children:
            return
        next_node = node.children[ch]
        if next_node.word:
            result.add(next_node.word)
        board[r][c] = '#'
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            pass  # DFS in 4 directions
        board[r][c] = ch
    
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, 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(len(findWords(board, words)))

Output

Ready. Press ▶ Run or Ctrl+Enter.

›