Description

Submission

class Solution {
    struct TrieNode{
        TrieNode* next[26];
        bool isEnd;

        TrieNode() {
            isEnd = false;
            for(int i = 0; i < 26; ++i) {
                next[i] = nullptr;
            }
        }
    };

    TrieNode* root;
    vector<string> rets;
    vector<string> hand;

    void dfs(string& s, int pos) {
        if(pos == s.length()) {
            string t;
            for(int i = 0; i < hand.size(); ++i) {
                t += hand[i];
                if(i != hand.size() - 1) t += " ";
            } 
            rets.push_back(t);
            return;
        }

        TrieNode* cur = root;
        string word;
        for(int i = pos; i < s.length(); ++i) {
            char ch = s[i];
            if(cur->next[ch-'a'] == nullptr) return;
            word.push_back(ch);
            cur = cur->next[ch-'a'];
            if(cur->isEnd) {
                hand.push_back(word);
                dfs(s, i + 1);
                hand.pop_back();
            }
        }
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        root = new TrieNode();

        for(auto& word: wordDict) {
            TrieNode* cur = root;
            for(auto& ch: word) {
                if(cur->next[ch-'a'] == nullptr) {
                    cur->next[ch-'a'] = new TrieNode();
                }
                cur = cur->next[ch-'a'];
            }
            cur->isEnd = true;
        }

        dfs(s, 0);
        return rets;
    }
};