Hard · Backtracking

Word Search II

Given an m × n grid of lowercase letters board and a list of distinct words, return, in any order, every word that can be spelled by a path of horizontally or vertically adjacent cells that uses each cell at most once.

Examples

Example 1

{
  "board": [
    ["o", "a", "a", "n"],
    ["e", "t", "a", "e"],
    ["i", "h", "k", "r"],
    ["i", "f", "l", "v"]
  ],
  "words": ["oath", "pea", "eat", "rain"]
}

Output: 2 words found

Example 2

{
  "board": [
    ["o", "a", "a", "n"],
    ["e", "t", "a", "e"],
    ["i", "h", "k", "r"],
    ["i", "f", "l", "v"]
  ],
  "words": ["oat", "oath", "at", "tat"]
}

Output: 3 words found

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.