70ms Concise C++ Solution Using Trie and Backtracking


  • 16

    Optimized to 70ms by pre-size the vec instead of push_back and pop_back

    class Solution {
    public:
        struct TrieNode {
            vector<int> indexs;
            vector<TrieNode*> children;
            TrieNode() {
                children.resize(26, nullptr);
            }
        };
    
        TrieNode* buildTrie(vector<string>& words) {
            TrieNode* root = new TrieNode();
            for (int j = 0; j < words.size(); j++) {
                TrieNode* t = root;
                for (int i = 0; i < words[j].size(); i++) {
                    if (!t->children[words[j][i] - 'a'])
                        t->children[words[j][i] - 'a'] = new TrieNode();
                    t = t->children[words[j][i] - 'a'];
                    t->indexs.push_back(j);
                }
            }
            return root;
        }
        
        vector<vector<string>> res;
        vector<string> vec;
        void backtrack(vector<string>& words, int level, TrieNode* root) {
            if (level >= words[0].size()) {
                res.push_back(vec);
                return;
            }
            string str = "";
            for (int i = 0; i < level; i++) 
                str += vec[i][level];
            TrieNode* t = root;     
            for (int i = 0; i < str.size(); i++) 
                if (!(t = t->children[str[i] - 'a'])) return;
            for (auto index : t->indexs) {
                vec[level] = words[index];
                backtrack(words, level + 1, root);
            }
        }
        
        vector<vector<string>> wordSquares(vector<string>& words) {
            if (words.empty()) return res;
            TrieNode* root = buildTrie(words);
            vec.resize((int)words[0].size());
            for (auto& word : words) {
                vec[0] = word;
                backtrack(words, 1, root);
            }
            return res;
        }
    };
    

  • 0
    D

    thanks for sharing. Got a question, do you need to record the words that have been used/visited?


  • 0

    @dong.han.1441 From the question's example, you can find that duplicates are allowed


  • 0
    S

    Might want to use smart pointers


  • 0
    Z

    Thanks for the solution! Here is my C++ with 2 optimization, 19ms 16/16.

    1. It is not necessary to build prefix string
    2. When building trie, we can stop before the last character.
    3. When building the word square row by row, every word in TrieNode.prefix is a possible answer. The code tries each word in a backtracking/DFS fashion.
    class Solution {
    struct TrieNode {
        // prefix is to keep indexes of all words that have the prefix from root to current node 
        vector<int> prefix;
        TrieNode* childs[26];
        TrieNode () {
            memset(childs, 0, sizeof(childs));
        }
    };
        
    public:
        vector<vector<string>> wordSquares(vector<string>& words) {
            int n = words[0].size();
            TrieNode* root = build(words);
            vector<vector<string>> ans;
            vector<string> board(n);
            for (int i = 0; i < words.size(); i++) {
                board[0] = words[i];
                helper(ans, board, words, root, 1);
            }
            return ans;
        }
    private:
        TrieNode* build(vector<string>& words) {
            TrieNode* root = new TrieNode();
            for (int i = 0; i < words.size(); i++) {
                TrieNode* p = root;
                for (int j = 0; j < words[i].size()-1; j++) {
                    if (p->childs[words[i][j]-'a'] == NULL) {
                        p->childs[words[i][j]-'a'] = new TrieNode();
                    }
                    p = p->childs[words[i][j]-'a'];
                    p->prefix.push_back(i);
                }
            }
            return root;
        }
        void helper(vector<vector<string>>& ans, vector<string>& board, vector<string>& words, TrieNode* root, int row) {
            if (row == board.size()) {
                ans.push_back(board);
                return;
            }
            TrieNode* p = root;
            for (int i = 0; i < row; i++) {
                if (p->childs[board[i][row]-'a'] == NULL) return;
                p = p->childs[board[i][row]-'a'];
            }
            // try every valid word, backtracking
            for (int i:p->prefix) {
                board[row] = words[i];
                helper(ans, board, words, root, row+1);
            }
        }
    };
    

  • 0

    @zestypanda said in 70ms Concise C++ Solution Using Trie and Backtracking:

    p->prefix.push_back(i);

    Could you illustrate more about the purpose of this line? what is its functional when using dfs? Thanks


  • 0
    Z

    @coder42 I put more comments in the post. Hopefully it explains.


  • 0
    Z

    May I get some help on how to analyze time complexity of this solution? Or generally how to analyze time complexity for trie solutions?


Log in to reply
 

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