Word Search

Try to solve the Word Search problem.

We'll cover the following

Statement#

Given an m×nm \times n 2D grid of characters and word as a string, we need to determine if the word can be constructed from letters of sequentially adjacent cells. The cells are considered sequentially adjacent when they are neighbors to each other either horizontally or vertically. The function should return TRUE if the word can be constructed and FALSE otherwise.

Constraints:

  • m == board.length
  • n == board[i].length, where 0≤0 \leq i << m
  • 1≤1 \leq m, n ≤6\leq 6
  • 1≤1 \leq word.length ≤15\leq 15
  • board and word consist of only lowercase or uppercase English letters.
  • The search is not case-sensitive.

Examples#

Created with Fabric.js 3.6.6 E D X I W P U F M Q I C A T E M A L C A J T I V E Sample example 1

1 of 6

Created with Fabric.js 3.6.6 E D X I W P U F M Q I C A T E M A L C A J T I V E Sample example 1

2 of 6

Created with Fabric.js 3.6.6 Sample example 2 O Y O I B I N A D Y P M M T W I Z I T C

3 of 6

Created with Fabric.js 3.6.6 Sample example 2 O Y O I B I N A D Y P M M T W I Z I T C

4 of 6

Created with Fabric.js 3.6.6 Sample example 3 h e c m l w l i e u a r r s n s i i o r

5 of 6

Created with Fabric.js 3.6.6 Sample example 3 h e c m l w l i e u a r r s n s i i o r

6 of 6

Understand the problem#

Let’s take a moment to make sure you've correctly understood the problem. The quiz below helps you check if you're solving the correct problem:

Word Search

1

Can we find the word magnanimousmagnanimous in the given grid?

[['K', 'I', 'C', 'D', 'L', 'J', 'M', 'R'] ['V', 'M', 'S', 'P', 'C', 'F', 'A', 'G'] ['C', 'A', 'G', 'D', 'J', 'O', 'L', 'O'] ['Q', 'Z', 'N', 'T', 'F', 'X', 'C', 'T'] ['R', 'L', 'A', 'N', 'I', 'R', 'G', 'D'] ['J', 'A', 'W', 'Y', 'M', 'O', 'U', 'A'] ['Z', 'A', 'P', 'D', 'R', 'C', 'S', 'D'] ['Y', 'V', 'A', 'F', 'P', 'L', 'Z', 'T']]
A)

Yes

B)

No

Question 1 of 20 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Start traversing the grid from the first cell.

Call depth-first search to search for the next character of the search word in the four possible directions for each cell of the grid.

If a valid character is found, call the depth-first search function again for this cell.

Continue searching through the cells until either the search word is found or all cells in the grid have been visited.

Try it yourself#

Implement your solution in main.py in the following coding playground. You will need the provided supporting code to implement your solution. We have also provided a useful code template that you may build on to solve this problem.

Python
main.py
neighbors.py
backtracking.py
Input #1
Input #2
Word Search

Backtracking: Introduction

Solution: Word Search