Word Search II
Hard · Tries
You are given a grid of single-character strings and a list of candidate words. A word can be traced by moving between horizontally or vertically adjacent cells, and no cell may be reused within the same traced word. Return every candidate word that can be formed this way somewhere on the grid. Each qualifying word should appear only once in the result, regardless of how many paths spell it.
Examples
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["oath","eat"]
Why: "oath" and "eat" can each be traced through adjacent cells without reusing a cell; "pea" and "rain" cannot be formed.Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
Why: Tracing "abcb" would require reusing the cell containing 'b', which is not allowed.Input: board = [["a","a"]], words = ["a","aa"]
Output: ["a","aa"]
Why: "a" is found at either cell, and "aa" is found by moving from the left cell to the right cell.Constraints
1 <= board.length, board[0].length <= 12, board[i][j] is a lowercase English letter, 1 <= words.length <= 3*10^4, 1 <= words[i].length <= 10, words[i] consists of lowercase English letters, all words[i] are distinct
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Word Search II. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.