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
| class TrieNode { public TrieNode[] children = new TrieNode[26]; public String word = null; }
class Trie { public TrieNode root = new TrieNode(); public void insert(String word) { TrieNode node = root; for (int i = 0; i < word.length(); ++i) { int charNo = word.charAt(i) - 'a'; if (node.children[charNo] == null) { node.children[charNo] = new TrieNode(); } node = node.children[charNo]; } node.word = word; } }
public class Solution {
public List<String> findWords(char[][] board, String[] words) { Trie trie = new Trie(); for (String word : words) { trie.insert(word); }
boolean[][] visited = new boolean[board.length][board[0].length]; Set<String> resultSet = new HashSet<>();
for (int i = 0; i < board.length; ++i) { for (int j = 0; j < board[0].length; ++j) { search(board, visited, i, j, board.length, board[0].length, trie.root, resultSet); } } return new ArrayList<>(resultSet); }
private void search(char[][] board, boolean[][] visit, int i, int j, int x, int y, TrieNode node, Set<String> result) { if (i < 0 || j < 0 || i >= x || j >= y || visit[i][j]) { return; } node = node.children[board[i][j] - 'a']; if (node == null) { return; } if (node.word != null) { result.add(node.word); }
visit[i][j] = true; search(board, visit, i - 1, j, x, y, node, result); search(board, visit, i + 1, j, x, y, node, result); search(board, visit, i, j - 1, x, y, node, result); search(board, visit, i, j + 1, x, y, node, result); visit[i][j] = false; } }
|