Word Search

Medium Solved

Description

Given an m × n grid of characters board and a string word, return true if the 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.

Input format / Clarification:

  • Line 1: JSON 2D array representing the board
  • Line 2: String word

Examples

Input:

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

Output: true

Input:

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

Output: true

Input:

[["A","B"],["C","D"]] ABCD

Output: false

Note:

Your program must print only true or false so it can be compared with the expected output.

No submissions yet.

Discuss DFS + backtracking approach, visited marking, and pruning strategies.

Test Cases