140. Word Break II

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

struct Trie {
    Trie* next[26];
    bool isFinish;
public:
    Trie(): isFinish(false) {
        memset(next,0,sizeof(next));
    }

    void insert(const char* str) {
        if('a' <= *str and *str <= 'z') {
            if(!next[*str-'a']) next[*str-'a'] = new Trie();
            next[*str-'a']->insert(str + 1);
        } else isFinish = true;
    }

    bool has(char ch) {
        return next[ch-'a'];
    }

    Trie* get(char ch) {
        return next[ch-'a'];
    }
};
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        Trie* trie = new Trie();
        for(auto& s : wordDict) {
            trie->insert(s.c_str());
        }
        vector<string> res;
        string str = "";
        backTracking(res,s,trie,str,0);
        return res;
    }
    void backTracking(vector<string>& res, string& s, Trie* root, string tmp, int p) {
        if(p == s.length()) {
            tmp.pop_back();
            res.push_back(tmp);
            return;
        }
        Trie* trie = root;
        for(int i = p; i < s.length(); i++) {
            if(trie->has(s[i])) {  //if has next char in trie, move next
                trie = trie->get(s[i]);
                tmp += s[i];
                if(trie->isFinish) {
                    tmp += ' '; //if is end of string add space and make next word
                    backTracking(res, s, root, tmp, i + 1);
                    tmp.pop_back(); //remove space
                }
            } else return;
        }
    }
};