Leetcode 212. Word Search II
Problem Explanation:
The problem is about searching multiple words on a grid (or a 2D board), each of them created by adjoining the same or different cells of the grid board. The cell must be selected from the adjacent cells, which is the neighboring cells in a vertical or horizontal manner, with the constraint that the same cell or the same letter cannot be used more than once for a single word. The board and the list contain only lowercase letters.
Example:
Given a board and a list of words as: board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words = ["oath","pea","eat","rain"]
The word "oath" can be found adjacently on the board as "o" is in (0,0), "a" is (1,1), "t" is (1,2), and "h" is (2,1). Similarly, "eat" is also present while "pea" and "rain" are not.
So, the return value is ["oath","eat"]
During the search for each word in the given list on the board, firstly, the words are recorded in the Trie data structure for easy access. Then, starting from each cell in the grid, a depth-first search (DFS) is performed on the Trie tree. If the word found during DFS is present in Trie, it is added to the result and removed from Trie to avoid duplication.
Python Solution:
1 2python 3class TrieNode: 4 def __init__(self): 5 self.children = [None] * 26 6 self.word = None 7 8class Solution: 9 def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: 10 root = TrieNode() 11 12 for word in words: 13 node = root 14 for char in word: 15 index = ord(char) - ord('a') 16 if not node.children[index]: 17 node.children[index] = TrieNode() 18 node = node.children[index] 19 node.word = word 20 21 result = [] 22 for i in range(len(board)): 23 for j in range(len(board[0])): 24 self._dfs(board, i, j, node=root, result=result) 25 return result 26 27 def _dfs(self, board, i, j, node, result): 28 if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] == '#': 29 return 30 31 char = board[i][j] 32 index = ord(char) - ord('a') 33 child = node.children[index] 34 if not child: 35 return 36 37 if child.word: 38 result.append(child.word) 39 child.word = None 40 41 board[i][j] = '#' 42 for x, y in [(0, 1), (0, -1), (1, 0), (-1, 0)]: 43 self._dfs(board, i + x, j + y, child, result) 44 board[i][j] = char
The Trie is a useful data structure for problems involving a list of words or prefixes. The DFS is an algorithm for traversing or searching tree or graph data structures. The strategies learned in this problem can be applied in many scenarios.JavaScript Solution:
You can use the below JavaScript solution, which also uses the concept of a Trie and DFS to solve the problem:
1 2javascript 3class TrieNode { 4 constructor() { 5 this.children = {}; 6 this.word = null; 7 } 8 9 add(word) { 10 let node = this; 11 for (let char of word) { 12 if (node.children[char] === undefined) { 13 node.children[char] = new TrieNode(); 14 } 15 node = node.children[char]; 16 } 17 node.word = word; 18 } 19} 20 21const findWords = (board, words) => { 22 const res = []; 23 const root = new TrieNode(); 24 for (let word of words) { 25 root.add(word); 26 } 27 28 const dfs = (i, j, node) => { 29 if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || !node) return; 30 31 const char = board[i][j]; 32 const child = node.children[char]; 33 34 if (!child) return; 35 if (child.word !== null) { 36 res.push(child.word); 37 child.word = null; 38 } 39 40 board[i][j] = null; 41 dfs(i + 1, j, child); 42 dfs(i - 1, j, child); 43 dfs(i, j + 1, child); 44 dfs(i, j - 1, child); 45 board[i][j] = char; 46 } 47 48 for (let i = 0; i < board.length; i++) { 49 for (let j = 0; j < board[0].length; j++) { 50 dfs(i, j, root); 51 } 52 } 53 54 return res; 55}
Java Solution:
Similar to the Python and JavaScript solutions, the Java solution utilizes Trie and DFS:
1 2java 3class TrieNode{ 4 String word; 5 TrieNode[] children = new TrieNode[26]; 6} 7 8public List<String> findWords(char[][] board, String[] words) { 9 List<String> result = new ArrayList<>(); 10 TrieNode root = buildTrie(words); 11 12 for(int i = 0; i < board.length; i++){ 13 for(int j = 0; j < board[0].length;j++){ 14 dfs(board, i, j, root, result); 15 } 16 } 17 return result; 18} 19 20public void dfs(char[][] board, int i, int j, TrieNode node, List<String> result){ 21 char c = board[i][j]; 22 if(c == '#' || node.children[c - 'a'] == null) return; 23 24 node = node.children[c - 'a']; 25 26 if(node.word != null){ 27 result.add(node.word); 28 node.word = null; 29 } 30 31 board[i][j] = '#'; 32 33 if(i > 0) dfs(board, i - 1, j ,node, result); 34 if(j > 0) dfs(board, i, j - 1, node, result); 35 if(i < board.length - 1) dfs(board, i + 1, j, node, result); 36 if(j < board[0].length - 1) dfs(board, i, j + 1, node, result); 37 38 board[i][j] = c; 39} 40 41public TrieNode buildTrie(String[] words){ 42 TrieNode root = new TrieNode(); 43 for(String s : words){ 44 TrieNode node = root; 45 for(char c : s.toCharArray()){ 46 int i = c - 'a'; 47 if(node.children[i] == null) node.children[i] = new TrieNode(); 48 node = node.children[i]; 49 } 50 node.word = s; 51 } 52 return root; 53}
The solutions in Python, JavaScript, and Java are all similar in logic and contain the use of a Trie and DFS. All solutions repeatedly apply DFS to each cell in the board, and use a Trie to quickly look up whether the sequence of characters corresponds to a word.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.