# DFS + Backtracking with Trie-based Pruning

• #### Approach #1 Brute Force [Time Limit Exceeded]

Intuition And Algorithm

It's straightforward to check if each word can be constructed by concatenating characters in the given 2D char array using the solution
of Word Search. Iterate given words and apply DFS + Backtracking to each word. The Brute Force approach failed at the last test case.

C++

``````class Solution {
public:
bool dfs(const vector<vector<char>>& board, int x, int y, const string& word, int i, vector<vector<bool>>& visited) {
//current character does not match word[i], search failed
if (board[x][y] != word[i]) {
return false;
}
//find a match, search succeeded
if (i == static_cast<int>(word.size()) - 1) {
return true;
}
//mark current position visited
visited[x][y] = true;
const vector<vector<int>> dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int m = board.size(), n = board[0].size();
for (const auto& dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
//if next position is invalid or already visited(each character can be used only once)
if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny]) {
continue;
}
//continue to search on next position
if (dfs(board, nx, ny, word, i + 1, visited)) {
return true;
}
}
//unmark visited position when backtracking
visited[x][y] = false;
return false;
}
bool search(const vector<vector<char>>& board, const string& word) {
if (board.empty() || board[0].empty() || word.empty()) {
return false;
}
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
//2D flag array to keep track of visited position
vector<vector<bool>> visited(m, vector<bool>(n, false));
//perform dfs on every position
if (dfs(board, i, j, word, 0, visited)) {
return true;
}
}
}
return false;
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> res;
for (const auto& word : words) {
if (search(board, word)) {
res.push_back(word);
}
}
//remove duplicated words
res.erase(unique(res.begin(), res.end()), res.end());
return res;
}
};
``````

Complexity Analysis

• Time complexity : O(MNLenNum), where M = board.size(), N = board[0].size(),
Len = word.size(), Num = words.size(); there Num word to search, for each word, DFS algorithm takes O(Len)
to search for the given word and it need to perform DFS on every position in the 2D char array in the worst case.

• Space complexity : O(M * N), where M = board.size(), N = board[0].size(); we need additional 2D flag array
to keep track of already visited positions in the DFS process if board is not allowed to be modified. However, the storage overhead can be avoided if we modify the board in-place and recover each position when backtracking.

#### Approach #2 DFS + Backtracking using Trie-based pruning [Accepted]

Intuition And Algorithm

We use trie tree to speed up searching. Firstly, we build up a trie tree using given words. Like Word Search Problem, we still apply DFS + Backtracking to
each position of the 2D char array. During each search, pruning is performed by checking if currently concatenated word can be found in the trie tree as a prefix.
If so, DFS proceeds, or DFS will be discarded otherwise.

C++

``````class Solution {
public:
struct TrieNode {
bool is_word_;
TrieNode* children_[26];
TrieNode() : is_word_(false) {
//use reference to initialize children_
for (auto& child : children_) {
child = nullptr;
}
}
};
class Trie {
public:
Trie() {
root_ = new TrieNode();
}
void Insert(const string& word) {
TrieNode* curr = root_;
for (auto c : word) {
int i = c - 'a';
if (!curr->children_[i]) {
curr->children_[i] = new TrieNode();
}
curr = curr->children_[i];
}
curr->is_word_ = true;
}
void Build(const vector<string>& words) {
for (const auto& word : words) {
Insert(word);
}
}
bool IsPrefix(const string& prefix) const {
TrieNode* curr = root_;
for (auto c : prefix) {
int i = c - 'a';
if (!curr->children_[i]) {
return false;
}
curr = curr->children_[i];
}
return true;
}
bool Search(const string& word) const {
TrieNode* curr = root_;
for (auto c : word) {
int i = c - 'a';
if (!curr->children_[i]) {
return false;
}
curr = curr->children_[i];
}
return curr->is_word_;
}
private:
TrieNode* root_;
};
bool dfs(const vector<vector<char>>& board, int x, int y,
string word, vector<vector<bool>>& visited, const Trie& trie, vector<string>& res) {
//word is found
if (trie.Search(word)) {
res.push_back(word);
}
//mark current position as visited
visited[x][y] = true;
const vector<vector<int>> dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int m = board.size(), n = board[0].size();
for (const auto& dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
//skip if next position is invalid, or already visited, or newly concatenated word is not a prefix
if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny] || !trie.IsPrefix(word + board[nx][ny])) {
continue;
}
//proceed searching
if (dfs(board, nx, ny, word + board[nx][ny], visited, trie, res)) {
return true;
}
}
//unmark visited position when backtracking
visited[x][y] = false;
return false;
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
if (board.empty() || board[0].empty() || words.empty()) {
return {};
}
Trie trie;
trie.Build(words);
vector<string> res;
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
//2D flag array to keep track of visited positions
vector<vector<bool>> visited(m, vector<bool>(n, false));
string word(1, board[i][j]);
dfs(board, i, j, word, visited, trie, res);
}
}
//remove duplicate words
sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
return res;
}
};
``````

Complexity Analysis

• Time complexity :

• Space complexity :

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.