My C++ Trie + Backtrace based solution (48 ms)


  • 25
    D

    The idea is to use a Trie to build a prefix tree for words to simplify the search and do DFS to search all the possible strings.
    For Trie, 26 pointers to point the sub-strings and a bool leaf to indicate whether the current node is a leaf (i.e. a string in words) and also idx is used to save the index of words for the current node.
    For DFS, just check if the current position is visited before (board[i][j]=='X'), if so, return, check if there is a string with such prefix (nullptr == root->children[words[idx][pos]-'a']), if not, return; otherwise, check if the current searched string is a leaf of the trie (a string in words), if so, save it to res and set leaf of the trie node to false to indicate such string is already found. At last, move to its neighbors to continue the search. Remember to recover the char [i][j] at the end.

        class Solution {
            class Trie{
            public:
                Trie *children[26]; // pointers to its substrings starting with 'a' to 'z'
                bool leaf; // if the node is a leaf, or if there is a word stopping at here
                int idx; // if it is a leaf, the string index of the array words
                Trie()
                {
                    this->leaf = false;
                    this->idx = 0;
                    fill_n(this->children, 26, nullptr);            
                }
            };
            
        public:
            void insertWords(Trie *root, vector<string>& words, int idx)
            {
                int pos = 0, len = words[idx].size();
                while(pos<len)
                {
                    if(nullptr == root->children[words[idx][pos]-'a']) root->children[words[idx][pos]-'a'] = new Trie();
                    root = root->children[words[idx][pos++]-'a'];
                }
                root->leaf = true;
                root->idx = idx;
            }
            
            Trie *buildTrie(vector<string>& words)
            {
                Trie *root = new Trie(); 
                int i;
                for(i=0; i<words.size();i++) insertWords(root, words, i);
                return root;
            }
            
            void checkWords(vector<vector<char>>& board, int i, int j, int row, int col, Trie *root, vector<string> &res, vector<string>& words)
            {
                char temp;
                if(board[i][j]=='X') return; // visited before;
                if(nullptr == root->children[board[i][j]-'a']) return ; // no string with such prefix
                else
                {
                    temp = board[i][j];
                    if(root->children[temp-'a']->leaf)  // if it is a leaf
                    {
                        res.push_back(words[root->children[temp-'a']->idx]);
                        root->children[temp-'a']->leaf = false; // set to false to indicate that we found it already
                    }
                    board[i][j]='X'; //mark the current position as visited
    // check all the possible neighbors
                    if(i>0) checkWords(board, i-1, j, row, col, root->children[temp-'a'], res, words);
                    if((i+1)<row) checkWords(board, i+1, j, row, col,  root->children[temp-'a'], res, words);
                    if(j>0) checkWords(board, i, j-1,  row, col, root->children[temp-'a'], res, words);
                    if((j+1)<col)  checkWords(board, i, j+1,  row, col, root->children[temp-'a'], res, words);
                    board[i][j] = temp; // recover the current position
                }
            }
        
            vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
               vector<string> res;
               int row = board.size();
               if(0==row) return res;
               int col = board[0].size();
               if(0==col) return res;
               int wordCount = words.size();
               if(0==wordCount) return res;
               
               Trie *root = buildTrie(words);
               
               int i,j;
               for(i =0 ; i<row; i++)
               {
                   for(j=0; j<col && wordCount > res.size(); j++)
                   {
                       checkWords(board, i, j, row, col, root, res, words);
                   }
               }
               return res;
            }
     };
    

    Based on the comments received. I created another version with Trie node counter (thanks, zhiqing_xiao and gxyeecspku). However, for the current test set, it doesn't help too much. Anyway, my version with Trie node counter.

    class Solution {
    private:
    class Trie
    {
    public:    
        Trie * children[26];
        bool isLeaf;
        int  wordIdx;
        int prefixCount;
        
        Trie()
        {
            isLeaf = false;
            wordIdx = 0;
            prefixCount = 0;
            fill_n(children, 26, nullptr);
        }
        
        ~Trie()
        {
            for(auto i=0; i<26; ++i) delete children[i];
        }
    };
        void insertWord(Trie *root,  const vector<string>& words, int idx)
        {
            int i, childID, len = words[idx].size();
            for(i=0, root->prefixCount++ ; i<len; ++i)
            {
                childID = words[idx][i]-'a';
                if(!root->children[childID]) root->children[childID] = new Trie();
                root = root->children[childID];
                ++root->prefixCount;
            }
            root->isLeaf = true; 
            root->wordIdx = idx;
        }
        
        Trie *buildTrie(const vector<string> &words)
        {
            Trie *root = new Trie();
            for(int i=0; i < words.size(); ++i) insertWord(root, words, i);
            return root;
        }
        
        int dfs_Trie(vector<string> &res, Trie *root, vector<vector<char>>& board, vector<string>& words, int row, int col)
        {
            int detected = 0;
    
            if(root->isLeaf)
            {
                ++detected;
                root->isLeaf = false;
                res.push_back(words[root->wordIdx]);
            }
            
            if( row<0 || row>=board.size() || col<0 || col>=board[0].size() || board[row][col]=='*' || !root->children[ board[row][col]-'a'] || root->children[ board[row][col]-'a']->prefixCount <= 0 ) return detected;
            int curC = board[row][col] - 'a';
            board[row][col] = '*';
            detected += dfs_Trie(res, root->children[curC], board, words, row-1, col) + 
                   dfs_Trie(res, root->children[curC], board, words, row+1, col) +    
                   dfs_Trie(res, root->children[curC], board, words, row, col - 1) +    
                   dfs_Trie(res, root->children[curC], board, words, row, col + 1) ;
            root->prefixCount -=detected;
            board[row][col] = curC+'a';
            return detected;
        }
        
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            int M, N, wordNum = words.size();
            vector<string> res;
            if( !(M = board.size()) || !(N = board[0].size()) || !wordNum) return res;
            Trie *root = buildTrie(words);
            for(auto i=0; i<M && root->prefixCount; ++i)
                for(auto j=0; j<N; ++j)
                    dfs_Trie(res, root, board, words, i, j);
            delete root;
            return res;
        }
    };

  • 0
    W

    which part in your code deals with avoiding duplicated words in res?
    Thanks.


  • 0
    N

    I guess with new test cases the time the run time of this code got slightly increased to 52 ms. Mine is giving 48 ms still but got that after lot of hacks and optimizations.


  • 6

    It would be better to deconstruct the Trie after using it.

    void destroyTrie(Trie* root)
    {
        if (root != nullptr)
        {
            for (int pos = 0; pos < 26; ++ pos)
            {
                destroyTrie(children[pos]);
            }
            delete root;
        }
        return;
    }
    

  • 4
    G

    I think Trie-based solution may be advanced by using a counter in each Trie node which counts the number of words in its child nodes that haven't been found, so that when a word or perfix appers many times in the board, repeated search can be avoided.

    public class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> strList = new LinkedList<String>();
        if (board.length == 0 || board[0].length == 0 || words.length == 0) return strList; 
        Trie trie = new Trie();
        for (String word : words) trie.add(word);
        TrieNode root = trie.root;
        StringBuffer strbuf = new StringBuffer();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                dfs(board, i, j, root, strbuf, strList);
            }
        }
        return strList;
    }
    private void dfs(char[][] board, int i, int j, TrieNode node, StringBuffer strbuf, List<String> strList) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] == ' ') return;
        TrieNode nextNode = node.next.get(board[i][j]);
        if (nextNode == null) return;
        strbuf.append(board[i][j]);
        board[i][j] = ' ';
        if (nextNode.isWord) {
            nextNode.isWord = false;
            TrieNode tmp = nextNode;
            do {	//update counter
                tmp.wordCnt--;
                tmp = tmp.pre;
            } while (tmp != null);
            strList.add(strbuf.toString());
        }
        if (nextNode.wordCnt > 0) {		//avoid repeated search
            dfs(board, i + 1, j, nextNode, strbuf, strList);
            dfs(board, i - 1, j, nextNode, strbuf, strList);
            dfs(board, i, j - 1, nextNode, strbuf, strList);
            dfs(board, i, j + 1, nextNode, strbuf, strList);
        }
        board[i][j] = strbuf.charAt(strbuf.length() - 1);
        strbuf.deleteCharAt(strbuf.length() - 1);
        
        return;
    }
    class TrieNode {
        boolean isWord;
        int wordCnt;	//counter of words haven't been found in the subtree
        TrieNode pre;	//parent of the node
        HashMap<Character, TrieNode> next;
        public TrieNode() {
            pre = null;
            isWord = false;
            wordCnt = 0;
            next = new HashMap<>();
        }
    }
    class Trie {
        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
        public void add(String word) {
            TrieNode tmp = root;
            char[] arr = word.toCharArray();
            for (char c : arr) {
                TrieNode next = tmp.next.get(c);
                if (next == null) {
                    next = new TrieNode();
                    next.pre = tmp;
                    tmp.next.put(c, next);
                }
                tmp = next;
            }
            if (tmp.isWord == false) {
                tmp.isWord = true;
                do {	//update counter
                    tmp.wordCnt++;
                    tmp = tmp.pre;
                } while (tmp != null);
            }
        }
    }
    

    }


  • 0
    D

    I think the following statement will do the work, thanks.
    root->children[temp-'a']->leaf = false; // set to false to indicate that we found it already


  • 0
    H

    good idea on duplicate avoiding.


  • 0
    N

    @gxyeecspku good idea, it will be fast.


Log in to reply
 

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