212. Word Search II
class TrieNode{ char val; TrieNode[] children; String word; public TrieNode(char x){ children = new TrieNode[26]; word = null; } } class Solution { public List<String> findWords(char[][] board, String[] words) { List<String> res = new ArrayList<>(); if(board == null || board.length == 0) return res; TrieNode root = new TrieNode(' '); buildTrie(root, words); for(int i = 0; i < board.length; i++){ for(int j = 0; j < board[0].length; j++){ char c = board[i][j]; if(root.children[c - 'a'] != null){ dfs(board, i, j, root, res); } } } return res; } private void buildTrie(TrieNode root, String[] words){ for(String s : words){ TrieNode cur = root; for(char c : s.toCharArray()){ if(cur.children[c - 'a'] == null){ cur.children[c - 'a'] = new TrieNode(c); } cur = cur.children[c - 'a']; } cur.word = s; } } private void dfs(char[][] board, int i, int j, TrieNode cur, List<String> res){ if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) return; char c = board[i][j]; if(c == '*') return; if(cur.children[c - 'a'] == null) return; cur = cur.children[c - 'a']; if(cur.word != null){ res.add(cur.word); cur.word = null; } board[i][j] = '*'; dfs(board, i + 1, j, cur, res); dfs(board, i - 1, j, cur, res); dfs(board, i, j + 1, cur, res); dfs(board, i, j - 1, cur, res); board[i][j] = c; } }