AlgoMonster: The Most Structured Way to Prepare for Coding Interviews

Word Search

Medium

Given an m x n board of characters and a word, return true if the word exists in the grid. The word can be constructed from letters in adjacent cells (horizontally or vertically) but cannot reuse the same letter cell more than once.

Example:

Input: 
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCCED"
Output: true

Input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "SEE"
Output: true

Input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCB"
Output: false

Test Cases

Input

3
A B C E
S F C S
A D E E
ABCCED

Expected Output

true

Step 1

Step 2

Step 3

Step 4

Step 1: Identify the Pattern

Brute Force1

Backtracking2

Dynamic Programming3

Breadth-First Search (BFS)4

Word Search

Medium

Example:

Input: 
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCCED"
Output: true

Input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "SEE"
Output: true

Input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCB"
Output: false

Test Cases

Input

3
A B C E
S F C S
A D E E
ABCCED

Expected Output

true

Step 1

Step 2

Step 3

Step 4

Step 1: Identify the Pattern

Brute Force1

Backtracking2

Dynamic Programming3

Breadth-First Search (BFS)4

Example:

Test Cases

Example:

Test Cases

Study Notes

Start Taking Notes!