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

牛群定位系统

https://www.nowcoder.com/practice/d808aaa4c13c4d38bff333aa796e6a1e

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

}

编程语言为Java。

该题考察的知识点是矩阵的深度优先搜索（DFS）算法，用于在二维字符数组中查找给定字符串是否存在。

代码的文字解释大纲如下：

在findWords方法中，创建一个空的字符串列表result，用于存储找到的匹配字符串。
使用增强型for循环遍历words数组中的每个字符串word。
调用私有方法exist，判断board中是否存在当前的word。如果存在，则将word添加到result列表中。
将result列表转换为字符串数组，并返回结果。
在Solution类中定义一个私有方法exist，接受一个char[][]类型的二维字符数组board和一个String类型的字符串word，返回一个布尔值。
定义变量rows和cols分别表示board数组的行数和列数。
创建一个布尔类型的二维数组visited，用于标记已访问的位置。初始化为false。
使用双层循环遍历board数组中的每个位置，通过调用私有方法dfs进行深度优先搜索，尝试匹配当前的word。
如果dfs方法返回true，则说明找到了匹配的字符串，返回true。
如果所有位置都没有找到匹配的字符串，返回false。
在Solution类中定义一个私有方法dfs，接受一个char[][]类型的二维字符数组board、一个String类型的字符串word、两个整数row和col分别表示当前位置的行和列索引、一个整数index表示当前匹配字符串的索引、一个布尔类型的二维数组visited用于标记已访问的位置，返回一个布尔值。
如果index等于word的长度，说明已经匹配完整个字符串，返回true。
如果当前位置越界、已经访问过、或者与当前word的字符不匹配，则返回false。
将当前位置标记为已访问。
定义四个方向的偏移量，分别表示向右、向左、向下、向上。使用增强型for循环遍历每个方向。
计算新的行和列索引，并递归调用dfs方法，传入新的位置信息，并将index加1。如果递归调用返回true，则说明找到了匹配的字符串，返回true。
将当前位置重新标记为未访问。
如果所有方向都没有找到匹配的字符串，返回false。
返回Solution类中的其他方法或变量。