DFS + Backtracking with Trie-based Pruning


  • 0
    S

    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 :


Log in to reply
 

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