题解 | #牛群定位系统#

知识点：dfs

思路：可以 StringBuilder 来动态构建字符串。我们遍历矩阵中的每个位置，并以该位置作为起点进行深度优先搜索。在搜索的过程中，我们构建当前的字符串，并与给定的单词列表进行匹配。如果匹配成功，我们将相应的单词标记为找到，并最终将标记为找到的单词加入结果列表中

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @param words string字符串一维数组
     * @return string字符串一维数组
     */
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, -1, 0, 1};

    public String[] findWords(char[][] board, String[] words) {
        int n = board.length;
        int m = board[0].length;
        Map<String, Integer> mp = new HashMap<>();
        for (String s : words) {
            mp.put(s, 0);
        }

        List<String> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                StringBuilder sb = new StringBuilder();
                dfs(sb, i, j, board, mp);
            }
        }

        for (String s : words) {
            if (mp.get(s) == 1) {
                res.add(s);
            }
        }

        return res.toArray(new String[0]);
    }

    private void dfs(StringBuilder sb, int x, int y, char[][] board,
                     Map<String, Integer> mp) {
        int n = board.length;
        int m = board[0].length;

        if (sb.length() > 12) return;

        sb.append(board[x][y]);
        String str = sb.toString();
        if (mp.containsKey(str)) {
            mp.put(str, 1);
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < m &&
                    Character.isAlphabetic(board[nx][ny])) {
                dfs(sb, nx, ny, board, mp);
            }
        }

        sb.deleteCharAt(sb.length() - 1);
    }
}