Trie + recursion + memorization


  • 1
    T

    The basic idea:

    • use Trie to store the dictionary.
    • then, use recursion to check all possible word break.
    • use memorization to avoid duplicate computation.

    Here is the code:

    class TrieNode {
        bool isWord;
        TrieNode * child[26];
    public:
        TrieNode() {
            isWord = false;
            for (int i = 0; i < 26; i++)
                child[i] = NULL;
        }
        bool isEnd() {
            return isWord;
        }
        void setEnd() {
            isWord = true;
        }
        TrieNode * getNode(char ch) {
            return child[ch - 'a'];
        }
        void setNode(char ch) {
            child[ch - 'a'] = new TrieNode();
        }
    };
    
    class Solution {
        TrieNode * root;
        vector<int> mem;
        int n;
        void addWord(string word) {
            TrieNode * pt = root;
            for (auto i : word) {
                if (!pt->getNode(i))
                    pt->setNode(i);
                pt = pt->getNode(i);
            }
            pt->setEnd();
        }
        
        //this function will return positions of all words align with s[pos...]
        vector<int> longestPrefix(const string & s, int pos) {
            TrieNode * pt = root;
            vector<int> res;
            while (pos < n) {
                if (!pt->getNode(s[pos]))
                    return res;
                pt = pt->getNode(s[pos]);
                if (pt->isEnd())//find one word, store its index and keep digging
                    res.push_back(pos);
                pos++;
            }
            return res;
        }
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            root = new TrieNode();
            for (auto i : wordDict)
                addWord(i);
            n = s.length();
            mem = vector<int> (n, 0);
            return wordBreak(s, 0);
        }
        bool wordBreak(const string & s, int pos) {
            if (mem[pos])
                return mem[pos] == 1 ? true : false;
            vector<int> res = longestPrefix(s, pos);
            if (!res.empty()) {
                for (auto i : res)
                    if (i == n - 1 || wordBreak(s, i + 1)) 
                        return mem[pos] = 1;
            }
            mem[pos] = -1;
            return false;
        }
    };
    

  • 0
    C

    When I use dfs + memoization ,It still pass all the test.But when I use trie + dfs, I got the TLE error.
    Do search in the trie really faster than the search in unordered_set?


Log in to reply
 

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