Facebook PixelWord Search — Coding Practice
Word SearchMedium

Word Search

Medium 15.4k44% acceptance
ArrayMatrixBacktrackingDepth-First Search

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

The path moves between horizontally or vertically adjacent cells, and the same cell may not be used more than once within a single word.

Example 1
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
A→B→C→C→E→D traces a connected path with no reused cell.
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
Reaching the second B would require reusing the first B cell.
Constraints
  • m == board.length, n == board[i].length
  • 1 ≤ m, n ≤ 6
  • 1 ≤ word.length ≤ 15
  • board and word consist of uppercase and lowercase English letters.
Asked atMicrosoftAmazonBloombergMeta
JavaScript
Loading editor…
Case 1
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED"
expected: true
Case 2
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"
expected: true
Case 3
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB"
expected: false
Case 4
[["A"]], "A"
expected: true
Case 5
[["A"]], "B"
expected: false
Case 6
[["A","B"],["C","D"]], "ABDC"
expected: true
Case 7
[["C","A","A"],["A","A","A"],["B","C","D"]], "AAB"
expected: true