1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

public static final int MAXN = 10001;
    public static int[][] tree = new int[MAXN][26];
    public static int[] pass = new int[MAXN];
    public static String[] end = new String[MAXN];
    public static int cnt;
    
    public static List<String> findWords(char[][] board, String[] words) {
        build(words);
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, 1, ans);
            }
        }
        clear();
        return ans;
    }
    
    public static int dfs(char[][] board, int i, int j, int t, List<String> ans) {
    // 边界检查：越界或者已访问过（board[i][j]==0表示已访问）
    if (i < 0 || i == board.length || j < 0 || j == board[0].length || board[i][j] == 0) {
        return 0;
    }
    
    char tmp = board[i][j];  // 保存当前字符，回溯时要恢复
    int road = tmp - 'a';     // 字符转换为路径编号
    t = tree[t][road];        // 在前缀树上走一步
    
    // 剪枝：如果前缀树这个节点下没有待匹配的单词了，直接返回
    if (pass[t] == 0) {
        return 0;
    }
    
    int fix = 0;  // 记录从这个位置开始找到了几个单词
    
    // 如果当前节点是某个单词的结尾，收集这个单词
    if (end[t] != null) {
        fix++;
        ans.add(end[t]);
        end[t] = null;  // 置空，避免重复收集
    }
    
    // 标记当前位置已访问（防止走回头路）
    board[i][j] = 0;
    
    // 向四个方向继续搜索
    fix += dfs(board, i - 1, j, t, ans);  // 上
    fix += dfs(board, i + 1, j, t, ans);  // 下
    fix += dfs(board, i, j - 1, t, ans);  // 左
    fix += dfs(board, i, j + 1, t, ans);  // 右
    
    // 回溯：恢复现场
    pass[t] -= fix;      // 更新这个节点下剩余的单词数
    board[i][j] = tmp;   // 恢复字符，供其他路径使用
    
    return fix;
}
    
    public static void build(String[] words) {
    cnt = 1;  // 节点编号从1开始，1是根节点
    for (String word : words) {
        int cur = 1;  // 从根节点开始
        pass[cur]++;  // 根节点下的单词数+1
        
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';  // 当前字符对应的路径编号
            if (tree[cur][path] == 0) {  // 如果这条路不存在
                tree[cur][path] = ++cnt;  // 创建新节点
            }
            cur = tree[cur][path];  // 走到下一个节点
            pass[cur]++;  // 这个节点下的单词数+1
        }
        end[cur] = word;  // 在单词结尾节点存储完整单词
    }
}
    
    public static void clear() {
        for (int i = 1; i <= cnt; i++) {
            Arrays.fill(tree[i], 0);
            pass[i] = 0;
            end[i] = null;
        }
    }