LeetCode 79(Golang): Word Search(Medium): DFS and Backtracking

Depth-First Search and Backtracking in Grid Traversal — An insightful exploration with LeetCode Problem 79.

Introduction

Are you intrigued by how words form winding paths in a two-dimensional grid? Or interested in understanding the connections between Depth-First Search (DFS) and backtracking? Come with me as we delve into the details of LeetCode problem no. 79 — “Word Search”. We’ll unravel the code and uncover the problem-solving gems of DFS and backtracking.

Problem

You can explore the detailed problem here on LeetCode. We are provided with a 2D grid (the board). Each cell in the grid comprises of a single letter. Our mission is to find whether a word exists in the grid by moving to any of the 4 adjacent cells (left, right, up, down), without revisiting any cell, and the cells must form the word in sequence.

Solution & Analysis

Here’s the solution to the problem using DFS and backtracking in the Go programming language:

This solution incorporates two crucial ideas: Depth-First Search and Backtracking.

Depth-First Search: DFS continues down a path till it can no longer find new nodes. It then backtracks to the previous node and explores the next available path. In our scenario, the DFS starts from each cell and keeps moving in a specified direction until it can’t form the word or is out-of-bounds.

Backtracking: This is where we “undo” a previously made choice that doesn’t lead to a solution. In our code, we temporarily mark each cell as visited by setting its value to ‘1’. We then explore all paths from that cell. If we don’t find the word, we backtrack by restoring the value of the cell, enabling it to be used in different paths.

The time complexity of our code is O(N * m * n) where N is the word’s length and m and n are the board’s dimensions: in the worst case, we’d traverse all cells for each letter in the word. The space complexity is O(m * n), required for the recursion stack in the worst case.

Analysis

Can you explain the specific process of DFS and backtracking

Depth-first Search (DFS) and Backtracking are powerful concepts widely used in various programming problems. To help you get an intuitive understanding of them, let’s dive deeper into how they play out in solving problems.

DFS (Depth-First Search)

Conceptually, DFS is like exploring a maze and it follows these steps:

1. Start: Choose a node or a position as a starting point. This could be the root of a tree, a corner of a grid, or the beginning of a string or array.
2. Move: From the current position, choose one path and keep moving along it. This can involve going deeper into a tree, ahead in an array, or to an adjacent cell in a grid, etc. DFS prefers going deeper along each path before exploring all the options at each level or node. This exploration along one route is sometimes referred to as “going down the rabbit hole.”
3. Check: While moving, keep checking if you’ve arrived at a solution or if you’ve reached a dead end. A dead end could be: end of an array, no nodes left in a branch of the tree, a non-promise cell on the grid, or a condition in the problem that marks a certain state as unsolvable.
4. Step Back: If you’ve hit a dead end or found a solution, step back (or “backtrack”) to the previous node or state and repeat the above process from Step 2.

Backtracking

Backtracking, in essence, is an algorithmic concept used to find all (or some) solutions to computational problems, notably constraint satisfaction problems. It incrementally builds candidates for the solutions and abandons a candidate as soon as it’s determined this cannot possibly be extended to a valid solution. Here are the general steps:

1. Make a Choice: Like a crossroads, at each step, you’re presented with multiple choices. You make a choice, hoping it’ll lead to a solution.
2. Consequences: You continue to solve the problem, taking the implications of that choice into account.
3. Check: If it’s determined that the current choice doesn’t lead to a valid solution (either by reaching a dead end or by violating a constraint), we have to discard that choice.
4. Undo the Choice (Backtrack): Go back to the point of choosing, revoke the previous choice, and make a different choice.

In many implementations, these two algorithms work hand-in-hand. DFS helps us to travel forward and explore, while backtracking enables us to step back and make a different choice when we reach a dead end.

For instance, while searching for a word in a grid (similar to the game Boggle), we start DFS from a cell in the grid. If the sequence of characters doesn’t form the word, we backtrack to try another direction. In this case, DFS helps us go down a path (sequence of characters), while backtracking helps us undo decisions (visited cells) when the path doesn’t form the word.

In what kind of problems can DFS and backtracking work?

Here are some categories of problems where DFS and Backtracking can be particularly useful:

1. Grid-Based Problems: Any problem involving exploration on a grid or matrix. This includes problems like the ‘Number of Islands’, ‘Word Search’, and ‘Rat in a Maze’.
2. Graph Traversal Problems: DFS is typically applied when you want to visit every single vertex in a graph, like ‘Traversal of Graph’ and ‘Finding Connected Components in a Graph’.
3. Tree-Based Problems: DFS approach helps solving binary tree problems such as ‘Max Depth of Binary Tree’, ‘Binary Tree Paths’, ‘Path Sum’, etc.
4. Coping Sequence Generation: Problems that involve generating combinations or permutations of a set, such as ‘Permutations’, ‘Combination Sum’, ‘Subsets’, etc. These problems make use of backtracking to explore different possible combinations or permutations.
5. Puzzle/Game-Based Problems: Problems that require finding a solution in a massive search-space. Classic examples including the ‘Sudoku solver’, ‘N Queens’, and ‘Knight’s Tour’.
6. Route/Path-Based Problems: Any problem that involves finding a path or sequence, such as ‘Given a string s, partition s such that every substring of the partition is a palindrome’, ‘All Paths from Source to Target’, etc.

It’s important to note that the benefit of using DFS and Backtracking in these problems is their efficiency in solving problems with high complexity. They effectively reduce the search space dynamically by ‘pruning’ paths that need not be visited or aren’t within constrains, allowing the algorithm to focus more on paths that could potentially lead to the solution.

Conclusion

In conclusion, DFS paired with backtracking become a great maneuver to navigate through grid-based traversal or path-finding problems like the “Word Search” problem on LeetCode. As we traced every potential path with DFS and pruned inefficient ones with backtracking, we minimized the search space and magnified the efficiency of our code.

I am keen to hear from you! Can you think of other problems that can be solved using these tactics? How do DFS and backtracking add up to solve them? Let’s continue our exploration in the comments below!