My 8ms C++ solution with Trie


  • 1
    Z
    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode() {
            memset(sons, 0, sizeof(TrieNode*) * 26);
            flg = false;
        }
        // char val;
        bool flg;
        TrieNode* sons[26];
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            if (word.size() == 0) return;
            TrieNode* t = root;
            for (int i = 0; i < word.size(); i++)
                if (t->sons[word[i] - 'a'])
                    t = t->sons[word[i] - 'a'];
                else
                    t = (t->sons[word[i] - 'a'] = new TrieNode());
            t->flg = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
            TrieNode* t = root;
            for (int i = 0; i < word.size(); i++)
                if (t->sons[word[i] - 'a'])
                    t = t->sons[word[i] - 'a'];
                else
                    return false;
            return (t-> flg);
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode* t = root;
            for (int i = 0; i < prefix.size(); i++)
                if (t->sons[prefix[i] - 'a'])
                    t = t->sons[prefix[i] - 'a'];
                else
                    return false;
            return true;
        }
    
    // private:
        TrieNode* root;
    };
    
    
    class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            int i, j;
            maxlen = 0;
            string curWord;
            res.clear(); curSol.clear(); //gList.resize(n);
            n = s.size();
            
            vector<bool> dp; dp.resize(n + 1, false); dp[0] = true;
            for (auto it = wordDict.begin(); it != wordDict.end(); ++it) trie.insert(*it);
            for (j = 0; j < n; j++) if (dp[j]){
                TrieNode* t = trie.root;
                for (i = j; i < s.size(); i++)
                    if (t->sons[s[i] - 'a'])
                    {
                        t = t->sons[s[i] - 'a'];
                        if (t->flg) dp[i + 1] = true;
                    }
                    else break;
            }
            if (dp[n]) DFS(0, s, dp);
            return res;
        }
    private:
        int n, maxlen;
        string curSol;
        vector<string> res;
        Trie trie;
        void DFS(int i, const string &s, const vector<bool> &dp){
            if (i == n) { res.push_back(curSol); return; }
            int tLen = curSol.size(), j;
            TrieNode* t = trie.root;
            if (i > 0) curSol.push_back(' ');
            for (j = i; j < n; j++){
                t = t->sons[s[j] - 'a'];
                if (t){
                    curSol.push_back(s[j]);
                    if (t->flg) DFS(j + 1, s, dp);
                } else break;
            }
            curSol.resize(tLen);
        }
    };

  • 0
    F

    I use trie and got AC too, but then I realized the problem doesn't say s and wordDict can't contain characters other than lowercase alphabet


Log in to reply
 

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