题解 | #牛群定位系统# 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) { 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;否则,回溯到上一层,并将当前字符标记为未访问。最终返回所有存在的单词组成的字符串数组。