单词搜索 II · 交互式算法学习

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1class Trie {2    Trie[] children = new Trie[26];3    int ref = -1;4 5    public void insert(String w, int ref) {6        Trie node = this;7        for (int i = 0; i < w.length(); ++i) {8            int j = w.charAt(i) - 'a';9            if (node.children[j] == null) {10                node.children[j] = new Trie();11            }12            node = node.children[j];13        }14        node.ref = ref;15    }16}17 18class Solution {19    private char[][] board;20    private String[] words;21    private List<String> ans = new ArrayList<>();22 23    public List<String> findWords(char[][] board, String[] words) {24        this.board = board;25        this.words = words;26        Trie tree = new Trie();27        for (int i = 0; i < words.length; ++i) {28            tree.insert(words[i], i);29        }30        int m = board.length, n = board[0].length;31        for (int i = 0; i < m; ++i) {32            for (int j = 0; j < n; ++j) {33                dfs(tree, i, j);34            }35        }36        return ans;37    }38 39    private void dfs(Trie node, int i, int j) {40        int idx = board[i][j] - 'a';41        if (node.children[idx] == null) {42            return;43        }44        node = node.children[idx];45        if (node.ref != -1) {46            ans.add(words[node.ref]);47            node.ref = -1;48        }49        char c = board[i][j];50        board[i][j] = '#';51        int[] dirs = {-1, 0, 1, 0, -1};52        for (int k = 0; k < 4; ++k) {53            int x = i + dirs[k], y = j + dirs[k + 1];54            if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] != '#') {55                dfs(node, x, y);56            }57        }58        board[i][j] = c;59    }60}