Skip to content
CodeShare
All problems

Word Search

Find a word in a grid of letters by moving between neighbors.

MediumBacktrackingMatrix

Given an m × n grid of characters board and a string word, return true if word can be traced in the grid.

The word is built from letters in sequentially adjacent cells, where adjacent means horizontally or vertically neighboring. The same cell can't be used twice in one word.

Examples

Example 1
Input
board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCCED"
Output
true
Example 2
Input
board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "SEE"
Output
true
Example 3
Input
board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCB"
Output
false
Why
Spelling ABCB would need to use the B twice.

Constraints

  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word contain only English letters.