题解 | #牛群定位系统# Java

> 转化为一个单词是否在数组中出现过, 结合visited数组进行dfs即可

findWords方法接受一个二维字符数组board和一个字符串数组words作为输入，并返回一个字符串数组。它通过遍历words数组中的每个单词，调用exist方法检查该单词是否在二维定位系统上出现，如果出现则将该单词添加到结果列表中。最后，将结果列表转换为字符串数组并返回。

exist方法用来检查一个单词是否在二维定位系统上出现。它接受一个二维字符数组board和一个字符串word作为输入，并返回一个布尔值。该方法使用深度优先搜索（DFS）来查找匹配的单词。首先，它获取二维数组的行数和列数，并创建一个与二维数组相同大小的布尔数组visited，用于标记已经访问过的字符。然后，它使用两个嵌套的循环遍历二维数组中的每个单元格，并在每个单元格中调用dfs方法进行搜索。如果dfs方法返回true，表示找到了匹配的单词，直接返回true。如果循环结束后仍未找到匹配的单词，则返回false。

dfs方法用来进行深度优先搜索。它接受一个二维字符数组board、一个字符串word、当前单元格的行索引row、当前单元格的列索引col、单词的当前字符索引index和一个布尔数组visited作为输入，并返回一个布尔值。首先，它检查当前字符索引是否等于单词长度，如果是，表示已经找到了匹配的单词，返回true。然后，它检查当前单元格的索引是否越界，是否已经访问过，以及当前单元格的字符是否与单词的当前字符相匹配。如果有任何一个条件不满足，返回false。接下来，将当前单元格标记为已访问，并定义一个方向数组，用于表示上、下、左、右四个方向的移动。然后，使用循环遍历四个方向，计算新的行索引和列索引，并递归调用dfs方法。如果递归调用返回true，表示在相邻单元格中找到了下一个匹配的字符，直接返回true。如果四个方向都没有找到匹配的字符，则将当前单元格标记为未访问，并返回false。

最终，调用方根据返回的结果确定哪些牛名在二维定位系统中出现，并按照在words中的出现顺序进行输出。

public class Solution {

    public String[] findWords (char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (exist(board, word)) {
                result.add(word);
            }
        }
        return result.toArray(new String[0]);
    }
    private boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, int row, int col, int index,
                        boolean[][] visited) {
        if (index == word.length()) {
            return true;
        }
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
                visited[row][col] || board[row][col] != word.charAt(index)) {
            return false;
        }
        visited[row][col] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            if (dfs(board, word, newRow, newCol, index + 1, visited)) {
                return true;
            }
        }
        visited[row][col] = false;
        return false;
    }
}