C++: Word Break

Thought Process

The Word Break problem requires determining if a string can be segmented into space-separated words from a given dictionary. Here are two approaches:

Approach 1: Dynamic Programming - First, we create a states array where states[i] indicates if substring s[0...i-1] is breakable or not. At each position, we check all dictionary words that could end there. If we find a word that matches and connects to a previous breakable state, we update the state accordingly. Finally, states[len] indicates whether a string of length 'len' is breakable or not.

Approach 2: Trie with Memoization - Here, we build a Trie from the dictionary words for efficient prefix searches. Further, we perform DFS (with memoization) & store results of subproblems in a map to avoid recomputation. After each valid word match, recursively check if the remaining substring can be broken or not.

Approach 1: Dynamic Programming 

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {

        int len = s.size();

        // states[i] tell whether string till ith index is breakable or not.
        vector<bool> states(len, false);
        states[0] = true;

        for (int i = 1; i <= len; i++) {

            for (int j = 0; j < wordDict.size(); j++) {

                string str = wordDict[j];
                int start = i - str.size();
                if (start >= 0 && states[start] == true && s.substr(start, str.size()) == str) {
                    states[i] = true;
                }
            }
        }
        return states[len];
    }
};

Approach 2: Trie with Memoization 

class Solution {
public:
    struct TrieNode {

        TrieNode* children[26];
        bool isLastCharacter;

        TrieNode() {
            isLastCharacter = false;
            for (int i = 0; i < 26; i++)
                children[i] = NULL;
        }
    };

    // Memorizing the solution to avoid calculating the overlapping sub
    // problems. It will tell whether a substring starting from ith character is
    // breakable or not.
    unordered_map<int, bool> mp;
    bool wordBreak(string s, vector<string>& wordDict) {

        TrieNode* root = new TrieNode();

        // Store all words of dictionary in the Trie
        for (int i = 0; i < wordDict.size(); i++) {

            string str = wordDict[i];
            insert(root, str);
        }

        bool isBreakable = search(root, s, 0);
        return isBreakable;
    }

    void insert(TrieNode* root, string str) {

        TrieNode* copy = root;
        for (int i = 0; i < str.size(); i++) {

            char ch = str[i];
            if (copy->children[ch - 'a'] == NULL)
                copy->children[ch - 'a'] = new TrieNode();

            copy = copy->children[ch - 'a'];
        }
        copy->isLastCharacter = true;
    }

    bool search(TrieNode* root, string str, int idx) {

        if (idx == str.size())
            return true;

        if (mp.contains(idx))
            return mp[idx];

        TrieNode* copy = root;
        for (int i = idx; i < str.size(); i++) {

            char ch = str[i];
            if (copy->children[ch - 'a'] == NULL) {
                mp.insert({i, false});
                return false;
            }
            copy = copy->children[ch - 'a'];

            if (copy->isLastCharacter) {

                // Now, once we memorize this sub problem, it will be used in
                // future iterations when search(root,str,i+1)--> false.
                if (search(root, str, i + 1)) {
                    mp.insert({i, true});
                    return true;
                }
            }
        }
        mp.insert({idx,false});
        return false;
    }
};

Code Complexity

Time Complexity: O(n3) for DP & O(n2) for Trie

DP approach has nested loops O(n2) with substring operations O(n). Trie approach reduces to O(n2) with memoization.

Space Complexity: O(n + m*k)

DP uses O(n) space, Trie uses additional space for dictionary storage where 'n' is string length, 'm' is dictionary size, and 'k' is average word length.

Code copied!