212. 单词搜索 II

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]

输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:

你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

先构建字典树，然后遍历board数组，匹配到字典树的字符进行深度优先遍历

class Solution {
    private char[][] board;
    private TrieNdoe root = new TrieNdoe();
    private Set<String> result = new HashSet<>();
    private int[][] dir = { // 上下左右
            {0, 1}, {0, -1}, {1, 0}, {-1, 0}
    };
    private boolean[][] used;

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        this.used = new boolean[board.length][board[0].length];
        for (String word : words) {
            insert(word);
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                findWord(i, j, root);
            }
        }
        return new ArrayList<>(result);
    }

    /**
     * DFS深度优先搜索
     *
     * @param row
     * @param column
     * @param node
     */
    private void findWord(int row, int column, TrieNdoe node) {
        char ch = board[row][column];
        int chIndex = ch - 'a';
        // 没找到 或者 已经使用过了
        if (node.nextNode[chIndex] == null || used[row][column]) {
            return;
        }
        // 如果找到一个word就记录下来
        if (node.nextNode[chIndex].endOfWord) {
            result.add(node.nextNode[chIndex].word);
        }
        // 记录当前位置已经使用过了
        used[row][column] = true;
        // 上下左右深度搜索
        for (int[] d : dir) {
            if (row + d[0] < 0 || row + d[0] >= board.length || column + d[1] < 0 || column + d[1] >= board[0].length) {
                continue;
            }
            findWord(row + d[0], column + d[1], node.nextNode[chIndex]);
        }
        // 回溯，将当前位置置为未使用过
        used[row][column] = false;
    }

    /**
     * 构建字典树
     */
    private void insert(String word) {
        TrieNdoe node = root;
        int chIndex;
        for (int i = 0; i < word.length(); i++) {
            chIndex = word.charAt(i) - 'a';
            if (node.nextNode[chIndex] == null) {
                node.nextNode[chIndex] = new TrieNdoe();
            }
            node = node.nextNode[chIndex];
        }
        node.endOfWord = true;
        node.word = word;
    }

    private class TrieNdoe {
        // 假设所有输入都由小写字母 a-z 组成
        public TrieNdoe[] nextNode = new TrieNdoe['z' - 'a' + 1];
        // 如果是最后的节点，才存
        public String word; 
        public boolean endOfWord;
    }

    public static void main(String[] args) {
        char[][] board = {{'a', 'b'}};
        new Solution().findWords(board, new String[]{"ba"});
    }
}