#0299

Word Search II

HardDSA40 min25 XP

Problem

Given a board and a list of words, return sorted words that can be formed by adjacent horizontal or vertical cells. A cell cannot be reused within one word.

Why This Matters

Word Search II combines tries with grid backtracking so failed prefixes are pruned early.

Function Signature

def find_words(board, words):

Examples

Example 1

Inputboard = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]

Output["eat", "oath"]

Only eat and oath can be traced on the board.

Constraints

Return the exact requested value.
Handle edge cases cleanly.
Use the intended DSA pattern when brute force would scale poorly.

CodePython

def find_words(board, words):
    """
    Input example: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
    Return: ["eat", "oath"]
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return []

def find_words(board, words):
    """
    Input example: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
    Return: ["eat", "oath"]
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return []

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

Two words found

Inputclassic board

Expected["eat", "oath"]

The trie prunes missing prefixes like pea.

No reuse

Inputsmall board

Expected[]

The same cell cannot be used twice.

Hidden Test Categories

shared word prefixesduplicate wordssingle-cell words