C++ Trie.. Not Simple as DP


  • 0
    class Solution {
        class Node {
        public:
            char c;
            unordered_map<char, Node*> next;
            bool isWord;
            Node(char c = '\0') : c(c), isWord(false) {}
            ~Node() {
                for (auto& i : next)
                    delete i.second;
            }
        };
        bool helper(string s, int index) {
            if (index == s.size())
                return true;
            if (dp.find(index) != dp.end())
                return dp[index];
            Node* cur = root;
            for (int i = index; i < s.size(); i++) {
                char c = s[i];
                if (cur->next.find(c) == cur->next.end())
                    return false;
                cur = cur->next[c];
                if (cur->isWord) {
                    bool f = helper(s, i + 1);
                    dp[i + 1] = f;
                    if (f)
                        return true;
                }
            }
            return false;
        }
        Node* root;
        unordered_map<int, bool> dp;
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            
            root = new Node();
            for (auto word : wordDict) {
                Node* cur = root;
                for (auto c : word) {
                    if (cur->next.find(c) == cur->next.end())
                        cur->next[c] = new Node(c);
                    cur = cur->next[c];
                }
                cur->isWord = true;
            }
            
            return helper(s, 0);
        }
        ~Solution() {
            delete root;
        }
    };
    

Log in to reply
 

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