题解 | #牛群定位系统#

题目考察的知识点是：

深度优先搜索和哈希算法。

题目解答方法的文字分析：

本题首先对数组进行遍历，判断二维数组中是否存在该元素，如果存在则加入到新的集合中，这个判断的逻辑则是一层套一层，然后用if去具体判断是否符合条件，最后得到需要的结果。

本题解析所用的编程语言：

java语言。

完整且正确的编程代码：

import java.util.*;


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