212. 单词搜索 II（字典树的另一种类型）

本文主要是介绍212. 单词搜索 II（字典树的另一种类型），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大致思路是：

根据words列表建立字典树，其中注意在单词末尾，将原来的isEnd变量换成存储这个单词的变量，方便存储到ans中，另外，字典树的字节点由原来的Trie数组变为hashmap，方便检索字母。

建立完字典树后，以board的每一个位置的字母为开头开始检索，如果能检索到某一个Trie节点的word属性不为空字符串，那么就是检索到了对应单词，将其存储在ans中。

检索方式为深度优先搜索，并对每个节点的上下左右的4个相邻节点进行进一步的深度优先搜索，这里要注意不要超出board边界。

另外ans的类型要设置为set类型，因为会存在前缀相同的情况。

在这里插入图片描述

class Solution {int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public List<String> findWords(char[][] board, String[] words) {Trie trie = new Trie();for (String word : words) {trie.insert(word);}// List<String> ans = new ArrayList<>();Set<String> ans = new HashSet<>(); // 注意ans的类型for (int i = 0; i < board.length; ++i) {for (int j = 0; j < board[0].length; ++j) {dfs(board, i, j, trie, ans);}}return new ArrayList<String>(ans);}private void dfs(char[][] board, int i, int j, Trie node, Set<String> ans) {if (!node.children.containsKey(board[i][j])) return;char ch = board[i][j];node = node.children.get(ch);if (node.word != "") ans.add(node.word);board[i][j] = '#'; // 标记已访问for (int[] dir : dirs) {int i2 = i + dir[0], j2 = j + dir[1];if (i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length){dfs(board, i2, j2, node, ans);   }}board[i][j] = ch; // 回溯到原来字符，因为正常是使用visited来标记已访问的元素的}
}class Trie {public String word;public Map<Character, Trie> children;// boolean isWord;public Trie() {this.word = "";this.children = new HashMap<>();}public void insert(String word) {Trie node = this;for (int i = 0; i < word.length(); ++i) {char c = word.charAt(i);if (!node.children.containsKey(c)) {node.children.put(c, new Trie());}node = node.children.get(c);}node.word = word;}
}