Word Search

Medium · Backtracking

You are given a rectangular grid of single letters and a target word. Determine whether the word can be traced out by moving from cell to adjacent cell (up, down, left, or right, no diagonals), using each cell of the grid at most once in the path. Return true if such a path exists, false otherwise.

Examples

Input:  board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Why:    Starting at the top-left A, moving right, right, down, down, left traces A-B-C-C-E-D.

Input:  board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Why:    Starting at the bottom-left S, moving up then right along E, E works.

Input:  board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Why:    After spelling ABC, the only adjacent B would require reusing the already-visited B cell.

Constraints

1 <= board.length, board[0].length <= 6, 1 <= word.length <= 15, board and word consist of uppercase and lowercase English letters

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.

Practise Word Search

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Word Search. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.