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;
    int mem[300];

    bool dfs(string& s, int pos) {
        if(mem[pos]) return false;
        if(pos == s.size()) return true;
        TrieNode* cur = root;
        for(int i = pos; i < s.size(); ++i) {
            char ch = s[i];
            if(cur->next[ch-'a'] != nullptr) {
                cur = cur->next[ch-'a'];
                if(cur->isEnd && dfs(s, i + 1)) return true;
            }
            else break;
        }

        mem[pos] = 1;
        return false;
    }
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        root = new TrieNode();

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

        return dfs(s, 0);
    }
};