0

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?

J. Doe
  • 1,291
  • 2
  • 10
  • 19
  • It doesn't look like backtracking to me. They're setting that node back to it's original value because they didn't find a result and that node may be part of a solution in another path. – Bakon Jarser Apr 04 '19 at 14:35
  • @BakonJarser, oh, so is it _not_ backtracking? I think this _is_ backtracking. – J. Doe Apr 04 '19 at 14:36
  • I was wrong about it not finding a result, it may have, but basically it's resetting the * on the board and if a result wasn't found it is going to go to the next spot on the board and try from there. If you look at a simple example like CBF, it wouldn't ever find the answer if you marked B as a * and left it there then moved on to C. – Bakon Jarser Apr 04 '19 at 14:48
  • @BakonJarser, yes, I totally get what the snippet is doing. But my question is this - why don't we start a DFS from the topmost left `A` (using a `visited` set just for this travel) and see if we can find `ABCCED`. If not, then start over from `B` (using a new `visited` set for this travel) and visit all the nodes and find new paths. – J. Doe Apr 04 '19 at 14:52

2 Answers2

0

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.

Samuel Bouffard
  • 26
  • 3
  • Thanks, but it does not answer my question. I understand what my snippet is doing. But my question is this - why don't we start a DFS from the topmost left A (using a visited set just for this travel) and see if we can find ABCCED. If not, then start over from B (using a new visited set for this travel) and visit all the nodes and find new paths. The necessity _to reset back the node to its original value_ was felt because we are doing backtracking. If we did a recursive DFS, we could have used a new `visited` set every time without any need for resetting. – J. Doe Apr 04 '19 at 14:57
  • I already did something along what you are talking about in a school project. The issue however is you need to keep a state of the frontier for every tree level along the path to your last recursive call. Which require O(dn) where d is the depth of your recursivity and n the size of your last frontier. The algo you shared prevent this memory usage + prevent the copy of the frontier for every recursive call. – Samuel Bouffard Apr 04 '19 at 15:10
  • 1
    @J.Doe Look at space-complexity and time-complexity of the proposed solution and the recursive DFs solution. See a difference? – Polygnome Apr 04 '19 at 15:22
0

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.

gus
  • 831
  • 6
  • 9
  • "_Your DFS will first try the right->down->left path_", why so? – J. Doe Apr 04 '19 at 21:16
  • Edited: Right, I've assumed the same order of exploring the neighbours in your DFS as it is in the code above. The code first goes right, then down, so it will first visit the 2x2 square. – gus Apr 04 '19 at 21:20