childNode = new TrieNode[26];
public void add(String word) {
if (word == null || word.length() == 0) {
for (char c : word.toCharArray()) {
if (curNode.childNode[index] == null) {
curNode.childNode[index] = new TrieNode();
curNode = curNode.childNode[index];
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
if (board == null || board.length == 0 || words == null || words.length == 0) {
for (String word : words) {
int m = board.length, n = board[0].length;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
StringBuilder word = new StringBuilder();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
searchWord(i, j, trie.root, word, words, directions, board, res);
public void searchWord(int row, int col, TrieNode node, StringBuilder word, String[] words, int[][] directions, char[][] board, List<String> res) {
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] == '#') {
char c = board[row][col];
TrieNode curNode = node.childNode[c - 'a'];
res.add(word.toString());
for (int[] direction : directions) {
int nextRow = row + direction[0];
int nextCol = col + direction[1];
searchWord(nextRow, nextCol, curNode, word, words, directions, board, res);
word.setLength(word.length() - 1);