Recall & Review
beginner
What is the main idea behind backtracking in the Word Search problem?
Backtracking tries to build the word letter by letter by exploring all possible paths in the grid. If a path does not lead to the full word, it goes back (backtracks) and tries another path.
Click to reveal answer
beginner
In the Word Search problem, why do we mark cells as visited during backtracking?
We mark cells as visited to avoid using the same cell more than once in the current word path, preventing cycles and incorrect matches.
Click to reveal answer
beginner
What are the typical directions explored from a cell in the Word Search grid?
From each cell, we explore up, down, left, and right neighbors to find the next letter in the word.
Click to reveal answer
beginner
How does the backtracking function know when to stop and return true?
When the current index reaches the length of the word, it means all letters have been matched successfully, so it returns true.
Click to reveal answer
intermediate
What is the time complexity of the Word Search backtracking solution in the worst case?
The worst-case time complexity is O(N * 3^L), where N is the number of cells in the grid and L is the length of the word. This is because from each cell, we explore up to 3 directions (excluding the direction we came from) for each letter.
Click to reveal answer
Which of these is NOT a valid move direction in the Word Search backtracking?
✗ Incorrect
The Word Search problem typically allows moves only up, down, left, and right, not diagonal.
Why do we need to unmark a cell as visited after exploring a path?
✗ Incorrect
Unmarking allows the cell to be reused in different search paths for other parts of the word.
What does it mean if the backtracking function returns false?
✗ Incorrect
Returning false means the current path cannot complete the word, so backtracking tries other paths.
What is the first step in the Word Search backtracking algorithm?
✗ Incorrect
We start backtracking from each cell to find the word starting at that position.
If the word length is 1, what is the simplest check to find it in the grid?
✗ Incorrect
If the word has one letter, just check if any cell contains that letter.
Explain how backtracking works to find a word in a grid step-by-step.
Think about trying paths and going back if stuck.
You got /7 concepts.
Describe why marking cells as visited and unvisited is important in the Word Search backtracking.
Consider what happens if you don't mark cells.
You got /4 concepts.