C++ solution using two Trie, time & memory efficient.


  • 8
    F

    This is easy to understand.

    struct Trie {
        vector<int> words; // index of words
        vector<Trie *> children;
        Trie() {
            children = vector<Trie *>(26, nullptr);
        }
        // Thanks to @huahualeetcode for adding this in case of memory leak
        ~Trie() {
            for (int i = 0; i < 26; i++) {
                if (children[i]) {
                    delete children[i];
                }
            }
        }
        
        void add(const string &word, size_t begin, int index) {
            words.push_back(index);
            if (begin < word.length()) {
                if (!children[word[begin] - 'a']) {
                    children[word[begin] - 'a'] = new Trie();
                }
                children[word[begin] - 'a']->add(word, begin + 1, index);
            }
        }
        
        vector<int> find(const string &prefix, size_t begin) {
            if (begin == prefix.length()) {
                return words;
            } else {
                if (!children[prefix[begin] - 'a']) {
                    return {};
                } else {
                    return children[prefix[begin] - 'a']->find(prefix, begin + 1);
                }
            }
        }
    };
    
    class WordFilter {
    public:
        WordFilter(vector<string> words) {
            forwardTrie = new Trie();
            backwardTrie = new Trie();
            for (int i = 0; i < words.size(); i++) {
                string word = words[i];
                forwardTrie->add(word, 0, i);
                reverse(word.begin(), word.end());
                backwardTrie->add(word, 0, i);
            }
        }
        
        int f(string prefix, string suffix) {
            auto forwardMatch = forwardTrie->find(prefix, 0);
            reverse(suffix.begin(), suffix.end());
            auto backwardMatch = backwardTrie->find(suffix, 0);
            // search from the back
            auto fIter = forwardMatch.rbegin(), bIter = backwardMatch.rbegin();
            while (fIter != forwardMatch.rend() && bIter != backwardMatch.rend()) {
                if (*fIter == *bIter) {
                    return *fIter;
                } else if (*fIter > *bIter) {
                    fIter ++;
                } else {
                    bIter ++;
                }
            }
            return -1;
        }
        
    private:
        Trie *forwardTrie, *backwardTrie;
    };
    

  • 0
    B

    This answer is brilliant!


  • 0
    H

    Nice solution!
    You should delete children to prevent memory leak.


  • 0

    I like your solution to balance time and space usage. I never thought about the extreme time or space usage solutions as in many other posts are actually practical, but it might depend on the restrictions defined in the problem..


  • 0
    M

    @Frank_Fan Nice solution. As the length of prefix or suffix is at most 10, the depth of Trie can be limited to 10 for further reduction of space and time complexity.


  • 0
    Z

    I think the destructor of TrieNode just delete all the child node of the trie,it doesn't free the root node.and You maybe also need a destructor in the class WordFilter .(maybe i think wrong ..lol)
    I used a recursive method as follow:

        void deleteTrie(TrieNode* rootx){
            if(!rootx) return;        
            for(auto curr:rootx->next){
                if(curr) deleteTrie(curr);  
            }
            //cout<<"delete_content: "<<rootx->content<<endl;
            delete(rootx);
        }   
    
    

    hope anyone understand how to implement the destructor can give some advice!


  • 1
    H

    @ZJUCool
    The updated deconstructor of Trie works fine, just need to delete the roots to actually invoke it which should be done in the deconstructor of WordFilter.

    ~WordFilter() {
      delete forwardTrie;
      forwardTrie = nullptr;
      delete backwardTrie;
      backwardTrie = nullptr;
    }
    

    Or creating roots on stack instead of heap, then no need to "explicitly delete" them.

    private:
      Trie forwardTrie;
      Trie backwardTrie;
    

  • 0
    Z
    This post is deleted!

  • 0
    H

    @ZJUCool

    When deleting root, Trie::~Trie(root) will be called, it will delete all root's children and Trie::~Tire(root->children[i]) will be called, .... Thus all children will be deleted recursively.
    You can try example here http://cpp.sh/8vdyv


Log in to reply
 

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