Word Search II Problem


Description

LeetCode Problem 212. Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

1
2
3
4
5
6
7
8
9
-----------------
| o | a | a | n |        o---a   a   n          o   a   a   n  
-----------------            |
| e | t | a | e |        e   t   a   e          e   t---a---e 
-----------------            |
| i | h | k | r |        i   h   k   r          i   h   k   r 
-----------------
| i | f | l | v |        i   f   l   v          i   f   l   v 
-----------------
1
2
3
Input:  board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
        words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]


Solution

Trie and Backtracking Approach

We can use the data structure trie to store the words. Then for each character in the board, we can use backtracking to search whether we can construct a word starting from this character.

We first build a trie structure that stores the list of words. In every trie node, we use an array of length 26 to store possible next trie node, and a flag to indicate whether the trie node is the last letter of a word in the dictionary. We also use a string to store the string formed by the trie nodes starting from the root node.

Suppose we have a list of words like this, words = [“oath”,”pea”,”eat”,”rain”]. The trie structure we build looks like the following. If the node is an end of a word, there is a * next to it.

1
2
3
4
5
6
7
e   o   p   r
|   |   |   |
a   a   e   a
|   |   |   |
t*  t   a*  i
    |       |
    h*      n*

Next, for each character in the board, we use backtracking to search whether we can construct a word starting from this character.

In each cell of the board, we mark this cell as visited, then we search the four neighboring cells. During the search, if the current cell has been visited, or does not exist in the trie, we backtrack. If we reach the end of a word in the trie, we find a solution.


Sample C++ Code

This is a C++ implementation of the trie and backtracking approach.

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> ans;

struct TrieNode {
    TrieNode* arr[26];
    bool is_end;
    string word;
    TrieNode() {
        for (int i = 0; i < 26; i ++) {
            arr[i] = NULL;
        }
        is_end = false;
    }
};

void insert(TrieNode* root, string key) {
    TrieNode* curr = root;
    for (int i = 0; i < key.size(); i ++) {
        int idx = key[i] - 'a';
        if (curr->arr[idx] == NULL)
            curr->arr[idx] = new TrieNode();
        curr = curr->arr[idx];
    }
    curr->is_end = true;
    curr->word = key;
}

void backtrack(vector<vector<char>>& board, TrieNode* root, int x, int y) {
    if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size())
        return;
    
    char c = board[x][y];
    if (c == '.') return;
    if (root->arr[c-'a'] == NULL) return;
    
    board[x][y] = '.';
    if (root->arr[c-'a']->is_end == true) {
        ans.push_back(root->arr[c-'a']->word); 
        root->arr[c-'a']->is_end = false;
    }
    
    backtrack(board, root->arr[c-'a'], x-1, y);
    backtrack(board, root->arr[c-'a'], x+1, y);
    backtrack(board, root->arr[c-'a'], x, y-1);
    backtrack(board, root->arr[c-'a'], x, y+1);
    
    board[x][y] = c;
    
}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    int r = board.size(), c = board[0].size();
    
    TrieNode* root = new TrieNode();
    for (int i = 0; i < words.size(); i ++) {
        insert(root, words[i]);
    }
    
    for (int i = 0; i < r; i ++) {
        for (int j = 0; j < c; j ++) {
            backtrack(board, root, i, j);
        }
    }
    return ans;
}

int main() {
    vector<vector<char>> board;
    board.push_back({'o','a','a','n'});
    board.push_back({'e','t','a','e'});
    board.push_back({'i','h','k','r'});
    board.push_back({'i','f','l','v'});
    vector<string> words = {"oath","pea","eat","rain"};
    vector<string> ans = findWords(board, words);
    for (int i = 0; i < ans.size(); i ++)
        cout << ans[i] << endl;
}




Related Posts

Map Sum Pairs Problem

LeetCode 677. Design a map that allows you to do...

Palindrome Pairs Problem

LeetCode 336. Given a list of unique words, return all...

Design Add And Search Words Data Structure Problem

LeetCode 211. Design a data structure that supports adding new...

Word Break Problem

LeetCode 139. Given a string s and a dictionary of...

Word Break II Problem

LeetCode 140. Given a string s and a dictionary of...

Stream of Characters Problem

LeetCode 1032. Implement the StreamChecker class as follows. Constructor, initialize...