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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @param words string字符串一维数组
     * @return string字符串一维数组
     */
    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]);
    }

    /**
     * 在字符矩阵中搜索指定单词
     *
     * @param board   字符矩阵
     * @param word    指定单词
     * @param row     当前行索引
     * @param col     当前列索引
     * @param index   单词中的字符索引
     * @param visited 记录已访问的字符
     * @return 是否存在指定单词的路径
     */
    private boolean dfs(char[][] board, String word, int row, int col, int index,
                        boolean[][] visited) {
        // 已经匹配到单词的最后一个字符，说明存在满足条件的路径
        if (index == word.length()) {
            return true;
        }

        int rows = board.length;
        int cols = board[0].length;

        // 超出边界、已经访问过、当前字符不匹配的情况下，返回false
        if (row < 0 || row >= rows || col < 0 || col >= cols ||
                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;
    }

    /**
     * 判断字符矩阵中是否存在指定的单词
     *
     * @param board 字符矩阵
     * @param word  指定单词
     * @return 是否存在指定单词
     */
    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;
    }
}

编程语言是Java。

该题考察的知识点是回溯算法和深度优先搜索算法。

代码通过深度优先搜索算法来在字符矩阵中搜索指定的单词。遍历给定的单词数组，对每个单词进行搜索。在搜索过程中，使用递归的方式实现深度优先搜索，从每个字符开始，按照上下左右四个方向依次进行搜索。如果相邻字符匹配并且未被访问过，则继续进行递归搜索。如果搜索成功，即找到了满足条件的路径，返回true；否则，回溯到上一层，并将当前字符标记为未访问。最终返回所有存在的单词组成的字符串数组。