Word Search

Hard~25 min

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 neighboring. The same letter cell may not be used more than once.

Examples

Example 1
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Explanation: The path A→B→C→C→E→D traces through adjacent cells in the grid.
Example 2
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Explanation: The path S→E→E starts from board[1][3] and moves down and left.
Example 3
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Explanation: The path A→B→C requires revisiting B, but each cell can only be used once.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters
  • Expected time complexity: O(m × n × 4^L)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run