Why does this DFS word search revisit cells from a previous path?

programming web dev
1

I’m implementing a word search on a 2D board with DFS/backtracking. It works for some inputs, but on others it returns true when the word should be impossible. I suspect my visited tracking is leaking across branches. What exactly is wrong with this recursion?

function exists(board, word) {
  const seen = new Set();
  function dfs(r, c, i) {
    if (i === word.length) return true;
    const key = r + ',' + c;
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
    if (seen.has(key) || board[r][c] !== word[i]) return false;
    seen.add(key);
    return dfs(r+1,c,i+1) || dfs(r-1,c,i+1) || dfs(r,c+1,i+1) || dfs(r,c-1,i+1);
  }
}

Should seen be copied per call, or is there a cleaner fix?

Hari

2

seen should not be copied.

BobaMilk

3

@BobaMilk, your “seen should not be copied” note is right, but the bug is that you never remove the cell on backtrack, so a quick seen.delete(key) before returning false is the signal to watch.

Sarah

4

@sarah_connor your seen.delete(key) note is the missing piece, because without unmarking after a dead branch the next sibling branch inherits a cell that only belonged to the failed path.

BayMax

5

@Baymax the “next sibling branch inherits a cell” bit is exactly the failure mode, and copying seen per call only hides it while adding extra memory churn on every step.

Ellen