139. Word Break

Hint - DP

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        // Initialize a DP array to keep track of valid substrings

        // Iterate over each position in the string
        for ()
        {
            // Check each word in the dictionary
            for ()
            {
                // Ensure that the current index is sufficient to accommodate the word

                // Check if the current position `i` can be formed by the current word
                // We also need to ensure that `dp[i - word.size()]` is true if `i` is not the start of the string
                if ()
                {
                    // Check if the substring matches the current word
                    if ()
                    {
                        // Mark the current position as reachable
                        // No need to check further words for this position
                    }
                }
            }
        }
        // Return whether the entire string can be segmented into dictionary words
    }
};

• 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)$

Hint - Trie + Bottom-Up DP

class TrieNode {
public:
    // Indicates whether the node represents the end of a word
    // Array of child nodes, one for each letter of the alphabet

    TrieNode()
    {
        // Initialize the node as not the end of a word
        // Initialize all child pointers to nullptr
    }
};

class Solution {
private:
    // Root of the Trie

public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        // Build the Trie from the wordDict
        // Initialize a new Trie root
        for ()
        {
                // Convert character to index (0 for 'a', 1 for 'b', ..., 25 for 'z')
                // Create new TrieNode if needed
                // Move to the child node
            // Mark the end of the word
        }

        // Dynamic Programming array to store results of subproblems
        // Initialize DP array with false

        for ()
        {
            // Check if current position is valid (either start of string or can be reached by a valid word break)
            if ()
            {
                for ()
                {
                    // Break if the current character path does not exist in the Trie
                    // Move to the next TrieNode
                    // Mark as true if we reach the end of a valid word
                }
            }
        }
        // Return if the entire string can be segmented
    }
};

• 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;
    }
};