Java | Leetcode Java题解之第212题单词搜索II

题目：

题解：

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);}Set<String> ans = new HashSet<String>();for (int i = 0; i < board.length; ++i) {for (int j = 0; j < board[0].length; ++j) {dfs(board, trie, i, j, ans);}}return new ArrayList<String>(ans);}public void dfs(char[][] board, Trie now, int i1, int j1, Set<String> ans) {if (!now.children.containsKey(board[i1][j1])) {return;}char ch = board[i1][j1];Trie nxt = now.children.get(ch);if (!"".equals(nxt.word)) {ans.add(nxt.word);nxt.word = "";}if (!nxt.children.isEmpty()) {board[i1][j1] = '#';for (int[] dir : dirs) {int i2 = i1 + dir[0], j2 = j1 + dir[1];if (i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length) {dfs(board, nxt, i2, j2, ans);}}board[i1][j1] = ch;}if (nxt.children.isEmpty()) {now.children.remove(ch);}}
}class Trie {String word;Map<Character, Trie> children;boolean isWord;public Trie() {this.word = "";this.children = new HashMap<Character, Trie>();}public void insert(String word) {Trie cur = this;for (int i = 0; i < word.length(); ++i) {char c = word.charAt(i);if (!cur.children.containsKey(c)) {cur.children.put(c, new Trie());}cur = cur.children.get(c);}cur.word = word;}
}