Word Search

medium

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighbouring. The same letter cell may not be used more than once.

Test Cases

Copy an input into the main harness and Run to verify

Input

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Expected Output

true

Input

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Expected Output

true

Input

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Expected Output

false

Explanation: The B would have to be reused.

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consist of only lowercase and uppercase English letters.

Hints

Hint 1 — click to reveal

Backtracking: try each cell as a starting point and walk the word one letter at a time.

Hint 2 — click to reveal

Mark a cell as used before recursing and restore it afterwards — that restore is the 'backtrack'.

Java Compiler