java - 在 DFS 中将节点标记为已访问以进行词搜索

Question

这是 leetcode 上的单词搜索问题。我在下面提供了一张图片，可以很好地解释它。我的方法包括板上每个字母的 DFS（通过迭代双 for 循环），我这样做是为了让我的 dfs 函数可以从每个字母开始，我可以获得所有不同的单词。

我还通过传入一个布尔数组将节点标记为已访问，如果我已经看到该节点，则该值将更改为 true，如果它没有通向路径，则更改回 false。我想这就是我搞砸的地方。我不确定如何正确地将节点标记为此处已访问，如果不这样做，我会得到一个无限循环。

当我运行我的程序并打印出 dfs 正在构建的字符串时，我没有得到所有可能的字符串。这就是我想要弄清楚的，如何获得所有的字符串。

你也可以在 leetcode 中运行代码。谢谢！

class Solution {
    public boolean exist(char[][] board, String word) {
        
        if(board == null || word == null) {
            return false;
        }
        
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                List<Character> tempList = new ArrayList<>();
                tempList.add(board[i][j]);
                boolean[][] tempBoard = new boolean[board.length][board[0].length];
                if(wordExists(i, j, word, tempList, board, tempBoard)) {
                    return true;
                } 
                else{
                     tempList.remove(tempList.size() - 1);
                }
            }
        }   
        return false;
    }
    
    public static boolean wordExists(int sr, int sc, String word, List<Character> list, char[][] board, boolean[][] tempBoard) {
        StringBuilder sb = new StringBuilder();
        for(Character c : list) {
            sb.append(c);
        }
        
        System.out.println(sb.toString());
        
        if(word.equals(sb.toString())) {
            return true;
        }
        
        final int[][] SHIFTS = {
            {0,1},
            {1,0},
            {0,-1},
            {-1,0}
        };
        tempBoard[sr][sc] = true;
        for(int[] shift : SHIFTS) {
            int row = sr + shift[0];
            int col = sc + shift[1];
            
            if(isValid(board, row, col, tempBoard)) {
                list.add(board[row][col]);
                
                if(wordExists(row, col, word, list, board, tempBoard)) {
                    return true;
                }
                tempBoard[sr][sc] = false;
                list.remove(list.size() - 1);
            }
        }
        return false;
    }
    
    public static boolean isValid(char[][] board, int row, int col, boolean[][] tempBoard) {
        if(row >= 0 && row < board.length && col >= 0 && col < board[row].length && tempBoard[row][col] != true) {
            return true;
        }
        return false;
    }
    
}

标签： javaalgorithmrecursiongraphdepth-first-search