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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @param words string字符串一维数组
     * @return string字符串一维数组
     */
    public boolean dfs(char[][] board, boolean[][] panduan, String s, int x, int y,
                       int index) {
        if (index == s.length()) {
            return true;
        }
        if (x < 0 || x > board.length - 1 || y < 0 || y > board[0].length - 1 ||
                board[x][y] != s.charAt(index) || !panduan[x][y]) {
            return false;
        }
        panduan[x][y] = false;
        boolean flag1 = dfs(board, panduan, s, x + 1, y, index + 1);
        boolean flag2 = dfs(board, panduan, s, x - 1, y, index + 1);
        boolean flag3 = dfs(board, panduan, s, x, y + 1, index + 1);
        boolean flag4 = dfs(board, panduan, s, x, y - 1, index + 1);
        return flag1 || flag2 || flag3 || flag4;
    }

    public String[] findWords(char[][] board, String[] words) {
        Set<String> sset = new HashSet<>();
        List<String> ansList = new ArrayList<>();
        for (String p : words) {
            for (int i = 0; i < board.length; ++i) {
                for (int j = 0; j < board[0].length; ++j) {
                    boolean[][] panduan = new boolean[board.length][board[0].length];
                    for (int k = 0; k < board.length; k++) {
                        Arrays.fill(panduan[k], true);
                    }
                    if (dfs(board, panduan, p, i, j, 0) && !sset.contains(p)) {
                        sset.add(p);
                        ansList.add(p);
                    }
                }
            }
        }
        String[] ans = new String[ansList.size()];
        ans = ansList.toArray(ans);
        return ans;
    }
}

编程语言是Java。

该题考察的知识点是深度优先搜索（DFS）算法和哈希集合（HashSet）。

代码的文字解释：findWords接受一个字符型二维数组board和一个字符串数组words作为输入，并返回一个字符串数组。

在findWords方法中，首先创建一个空的哈希集合sset来存储已经找到的单词，以确保结果中没有重复的单词。接着使用两层for循环遍历words数组和board数组，对于每个单词p和每个board上的位置(i, j)，使用DFS搜索判断是否能从该位置出发找到单词p。为了避免重复搜索，使用一个布尔型二维数组panduan记录每个位置是否已经被访问过。

如果从当前位置(i, j)可以找到单词p，且sset中不存在该单词，那么将该单词加入sset并添加到结果数组ans中。