主题：使用回溯背后的直觉（而不仅仅是递归DFS）

Question

给定word=“abcced”，返回true。

一个被高度否决的解决方案如下：

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;
}

我的问题是--与使用普通递归DFS相比，使用回溯algo来解决这个问题背后的直觉是什么？在使用递归DFS时，我只需将节点标记为已访问节点，然后转移到它的邻居（因此发现abcced是有效路径）。为什么我必须回溯（上面代码中的注释行）来实现此路径是否存在？

Answer 1

深度优先搜索是一种回溯算法。递归性的本质是回溯机制本身。如果路径不是好路径，则在深入树之前返回一个false。以下是您的回溯：

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] = word.charAt(ind);

正如Bakon Jarser在问题帖子中评论的那样，它只是用来将节点重置回它的原始值，并允许它在其他相邻路径中使用。