C++ 22ms (beat 100%) trie solution


  • 0
    B

    I think the keypoint is we record which words share the same trie node (using index of the words)
    About the recursive rule is already explained by @StefanPochmann

    class Solution {
    public:
        struct trie {
            vector<trie*> child;
            vector<int> idx;
            trie() {
                child.resize(26, NULL);
            }
        };
        void square_find(vector<string>& words, trie *root, vector<vector<string>> &res, int pos, vector<string> &ans) {
            string key;
            trie *cur = root;
            int i;
            for (i = 0; i < pos; i++) {
                if (!cur->child[ans[i][pos] - 'a'])
                    break;
                cur = cur->child[ans[i][pos] - 'a'];
            }
            if (i != pos)
                return;
            
            for(int  id : cur->idx) {
                ans.push_back(words[id]);
                if(pos + 1 == words[id].size())
                    res.push_back(ans);
                else
                    square_find(words, root,res, pos + 1, ans);
                ans.pop_back();
            }
        }
        vector<vector<string>> wordSquares(vector<string>& words) {
            trie *root = new trie();
            vector<vector<string>> res;
            vector<string> ans;
            for(int j = 0; j < words.size(); j++) {
                trie *cur = root;
                string w = words[j];
                root->idx.push_back(j);
                for (int i = 0 ; i < w.size(); i++) {
                    if (!cur->child[w[i] - 'a'])
                        cur->child[w[i] - 'a'] = new trie();
                    cur = cur->child[w[i] - 'a'];
                    cur->idx.push_back(j);
                }
            }
            square_find(words, root, res, 0, ans);
            return res;
        }
    };
    

Log in to reply
 

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