My AC cpp solution using DP and Trietree Backtracking with 15ms.


  • 0
    L
    struct TrieNode{
        char val;
        bool isEnd;
        TrieNode* next[26] = {NULL};
        TrieNode(char x) : val(x), isEnd(false) {}
    };
    
    class TrieTree{
    private:
        TrieNode* root = new TrieNode('a');
    public:
        void trieInsert(string word){
            TrieNode* RootTemp = root;
            for(int i = 0; i < word.size(); i++){
                if(RootTemp->next[word[i]-'a'] == NULL){
                    RootTemp->next[word[i]-'a'] = new TrieNode(word[i]);
                    RootTemp = RootTemp->next[word[i]-'a'];
                }
                else{
                    RootTemp = RootTemp->next[word[i]-'a'];
                }
            }
            RootTemp->isEnd = true;
        }
        void getSentense(vector<string>& result, string& sentense, string s){
            string sentenseTemp = sentense;
            sentense.push_back(' ');
            TrieNode* RootTemp = root;
            for(int i = 0; i < s.size(); i++){
                if(RootTemp->next[s[i]-'a'] != NULL){
                    RootTemp = RootTemp->next[s[i]-'a'];
                    sentense.push_back(s[i]);
                    if(RootTemp->isEnd == true && i+1 != s.size()){
                        getSentense(result,sentense,string(s,i+1,s.size()-i-1));
                    }
                    else if(RootTemp->isEnd == true && i+1 == s.size()){
                            sentense.erase(sentense.begin());
                            result.push_back(sentense);
                         }
                }
                else{
                    sentense = sentenseTemp;
                    return;
                }
            }
            sentense = sentenseTemp;
        }
    };
    
    class Solution {
    public:
        bool isBreak(string s, unordered_set<string> &dict){
            if(dict.empty()) return false;
            vector<bool> canBreak(s.size()+1,false);
            canBreak[0] = true;
            for(int i = 1; i <= s.size(); i++){
                for(int j = i-1; j >= 0; j--){
                    if(canBreak[j] == true){
                        if(dict.find(string(s,j,i-j)) != dict.end()){
                            canBreak[i] = true;
                            break;
                        }
                    }
                }
            }
            return canBreak[s.size()];
        }
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
            vector<string>  result;
            TrieTree        myTrieTree;
            string          sentense;
            if(isBreak(s,dict)){
                for(auto& word : dict){
                    myTrieTree.trieInsert(word);
                }
                myTrieTree.getSentense(result, sentense, s);
                return result;
            }else return result;
        }
    };

Log in to reply
 

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