CODEWITHSUNDEEP
javaalgorithmdepth-first-searchbacktrackingrecursive-backtracking
J. Doe
J. Doe

Reputation: 1331

Topic: Intuition behind using backtracking (and not just recursive DFS)

For starters, I am not trying to ask the difference between a car and a DeLorean. So, I am solving this LeetCode question:

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

board =
[
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
]

Given word = "ABCCED", return true.

A highly upvoted solution is as follows:

public class Solution {
public boolean exist(char[][] board, String word) {
    for(int i = 0; i < board.length; i++)
        for(int j = 0; j < board[0].length; j++){
            if(exist(board, i, j, word, 0))
                return true;
        }
    return false;
}
private boolean exist(char[][] board, int i, int j, String word, int ind){
    if(ind == word.length()) return true;
    if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind))
        return false;
    board[i][j]='*';
    boolean result =    exist(board, i-1, j, word, ind+1) ||
                        exist(board, i, j-1, word, ind+1) ||
                        exist(board, i, j+1, word, ind+1) ||
                        exist(board, i+1, j, word, ind+1);
    board[i][j] = word.charAt(ind);     //--> why?
    return result;
}

My question is - what was the intuition behind using a backtracking algo for this question, as against using a normal recursive DFS? While using recursive DFS, I would just have marked the nodes as visited and then moved on to its neighbors (thereby figuring out ABCCED is a valid path). Why do I have to backtrack (commented line in code above) to realize if this path exists?

Thanks!

Edit: Other way of asking my question is this way: Why don't we start from the topmost left cell A and start visiting all its neighbors using a visited set along the way to mark visited nodes? In the next iteration, we could start from the cell adjacent to topmost left A - B, visit all its neighbors using a new visited set to mark visited nodes and so on? Why use backtracking?

Upvotes: 0

Views: 223

Answers (2)

gus
gus

Reputation: 821

Let's say you're looking for the word ABCBDE on this board:

ABD
BCE

Assuming the same order of neighbor exploration as in your supplied source code, your DFS will first try the right->down->left path, so your visited set will contain the leftmost 2x2 square and you will be blocked from finding the solution.

Upvotes: 0

Samuel Bouffard
Samuel Bouffard

Reputation: 26

Depth-first search is a backtracking algorithm. The nature of the recursivity is the backtracking mechanism itself. If the path is not the good one, it returns a false before going deeper in tree. Here is your backtracking:

if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind))
    return false;

The line

board[i][j] = word.charAt(ind);

is simply used to reset back the node to it's original value and allow it's use in an other adjacent path as Bakon Jarser commented on the question post.

You can check real quick first paragraph and this post.

Hope this help.

Upvotes: 0

Related Questions