C++ solution with Trie & Backtracking (DFS) with explanation


  • 0
    H

    The idea is to create the Trie of all words given. And once we are done building this trie, we iterate over the grid and when ever we see a character that is the beginning of a word in the list, we do a backtracking starting at this position. The only extra thing is to keep the trie node along with the recursion so that you know you are looking for a word thats present in the given list of words. So, whenever we see a character that is the starting character of any string in the words list, we backtrack from there looking for any possible word from the input words. And once we find one, make sure to mark it added otherwise we may get duplicates. Here is the code,

    class Solution {
    public:
        struct TrieNode{
            bool end;
            TrieNode* children[26];
            TrieNode(){
                end = false;
                for(int i = 0; i < 26; i++){
                    children[i] = NULL;
                }
            }
        };
        void insertIntoTrie(TrieNode* root, string s){
            int ix = 0, n = s.length();
            while(ix < n){
                int ins = s[ix] - 'a';
                if(root->children[ins] == NULL){
                    root->children[ins] = new TrieNode();
                }
                root = root->children[ins];
                ix ++;
                if(ix == n){
                    root->end = true;
                }
            }
        }
        void printTrie(TrieNode* root, string s){
            if(root == NULL){
                return;
            }
            if(root->end){
                cout<<s<<endl;
            }
            for(int i = 0; i < 26; i++){
                if(root->children[i] != NULL){
                    char p = i + 'a';
                    s.push_back(p);
                    printTrie(root->children[i], s);
                    s.pop_back();
                }
            }
        }
        bool isSafe(int x, int y, int m, int n){
            return x >= 0 && x < m && y >= 0 && y < n;
        }
        void solve(vector<vector<char>>& board, TrieNode* root, int x, int y, int m, int n, string curr, vector<string>& ret){
            if(!isSafe(x, y, m, n)) return;
            if(board[x][y] == '#') return;
            if(root == NULL) return;
            int d = board[x][y] - 'a';
            if(root->children[d] == NULL) return;
            char save = board[x][y];
            board[x][y] = '#';
            TrieNode* next = root->children[d];
            curr.push_back(save);
            if(next != NULL && next->end){
                next->end = false;
                ret.push_back(curr);
            }
            solve(board, next, x-1, y, m, n, curr, ret);
            solve(board, next, x, y-1, m, n, curr, ret);
            solve(board, next, x+1, y, m, n, curr, ret);
            solve(board, next, x, y+1, m, n, curr, ret);
            board[x][y] = save;
            curr.pop_back();
        }
        TrieNode* removeFromTrie(TrieNode* root, string rem, int i){
            if(i == rem.size()){
                if(allNull(root)){ 
                    return NULL;
                }
                return root;
            }
            int d = rem[i]-'a';
            TrieNode* tmp = removeFromTrie(root->children[d], rem, i+1);
            root->children[d] = tmp;
            if(allNull(root)) return NULL;
            return root; 
        }
        bool allNull(TrieNode* root){
    
            for(int i = 0; i < 26; i++){
                if(root->children[i] != NULL) return false;
            }
            return true;
        }
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            TrieNode* root = new TrieNode();
            vector<string> ret;
            int len = words.size();
            if(len == 0) return ret;
            int m = board.size();
            if(m == 0) return ret;
            int n = board[0].size();
            if(n == 0) return ret;
            for(string word: words){
                insertIntoTrie(root, word);
            }
            int retIx = 0;
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    int c = board[i][j] - 'a';
                    if(root!= NULL && root->children[c] != NULL){
                        string curr;
                        solve(board, root, i, j, m, n, curr, ret);
                        for(;retIx < ret.size(); retIx++){
                            string rem = ret[retIx];
                            root = removeFromTrie(root, rem, 0);
                            if(root == NULL) break;
                        }
                    }
                }
            }
            return ret;
        }
    };
    

    The remove from trie part is not needed, just making the root->end = false would suffice. But it gave me a 12ms speedup ;)


  • 0
    Q

    @harunrashidanver
    your program is roughly 73 ms. My program without remove from Trie is roughly 50ms. The main difference is that you create new string every time, while I used a fixed string REFERENCE and push_back and pop_back.


Log in to reply
 

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