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.