139. Word Break

DP

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        int n = s.size();
        vector<bool> dp(n);
        for (int i = 0; i < n; i++)
        {
            for (auto& word : wordDict)
            {
                if (i < word.size() - 1) continue;
                if (i == word.size() - 1 || dp[i - word.size()])
                {
                    if (s.substr(i - word.size() + 1, word.size()) == word)
                    {
                        dp[i] = true; break;
                    }
                }
            }
        }
        return dp.back();
    }
};

• T: $O(N \cdot M \cdot K)$
• S: $O(N)$

Trie + Bottom-Up DP

class TrieNode {
public:
    bool isWord;
    TrieNode* child[26];
    TrieNode()
    {
        isWord = false;
        for (int i = 0; i < 26; ++i)
        {
            child[i] = nullptr;
        }
    }
};

class Solution {
private:
    TrieNode* root = new TrieNode();
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        root = new TrieNode();
        for (auto w : wordDict)
        {
            TrieNode* node = root;
            for (auto c : w)
            {
                if (!node->child[c - 'a'])
                {
                    node->child[c - 'a'] = new TrieNode();
                }
                node = node->child[c - 'a'];
            }
            node->isWord = true;
        }

        vector<bool> dp(s.size());
        for (int i = 0; i < s.size(); i++)
        {
            if (i == 0 || dp[i - 1])
            {
                TrieNode* node = root;
                for (int j = i; j < s.size(); j++)
                {
                    char c = s[j];
                    if (!node->child[c - 'a'])
                    {
                        break;
                    }
                    node = node->child[c - 'a'];
                    if (node->isWord) dp[j] = true;
                }
            }
        }
        return dp[s.size() - 1];
    }
};

Trie + Top-Down DP

class TrieNode {
public:
    TrieNode* child[26];
    bool isWord;
    TrieNode()
    {
        isWord = false;
        for (int i = 0; i < 26; ++i)
        {
            child[i] = nullptr;
        }
    }
};

class Solution {
private:
    TrieNode* root;
    int memo[300];
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        root = new TrieNode();
        for (auto word: wordDict)
        {
            TrieNode* node = root;
            for (auto c : word)
            {
                if (!node->child[c - 'a'])
                {
                    node->child[c - 'a'] = new TrieNode();
                }
                node = node->child[c - 'a'];
            }
            node->isWord = true;
        }
        return dfs(s, 0);
    }

    bool dfs(string& s, int cur)
    {
        if (memo[cur] == 1) return false;

        if (cur == s.size()) return true;

        TrieNode* node = root;
        for (int i = cur; i < s.size(); ++i)
        {
            if (node->child[s[i] - 'a'])
            {
                node = node->child[s[i] - 'a'];
                if (node->isWord && dfs(s, i + 1))
                {
                    return true;
                }
            }
            else break;
        }

        memo[cur] = 1;
        return false;
    }
};