Word Break II

Problem

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.

Solution Approach

For at any index $i$ check for all words in the dictionary start from index $i$ in the string. If a word start at index $i$ append it to the sequence string and check for the subsequence of words starting from $j = i + word.length()$. If a valid sequence of words exit between the in indexes $j$ and $n$. Then append the sequence string to the ans vector.
Use Recursion to solve this problem

Expected Time complexity: $O(n^4)$

Click - to see solution code

C++

class Solution {
    unordered_map<string, int> word;
    string s;
    vector<string> thisOne;
    vector<vector<string>> ans;

   public:
    void compute(int indx) {
        if (indx == s.length()) {
            ans.push_back(thisOne);
            return;
        }

        for (auto i : word) {
            if (indx + i.first.length() > s.length()) continue;
            string w = s.substr(indx, i.first.length());
            if (i.first == w) {
                thisOne.push_back(w);
                compute(indx + w.length());
                thisOne.pop_back();
            }
        }
    }

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for (auto i : wordDict) word[i] = 1;
        this->s = s;
        vector<string> sen;
        string t;
        compute(0);
        for (auto i : ans) {
            string a = "";
            for (auto j : i) {
                a = a + j;
                a += ' ';
            }
            a.pop_back();
            sen.push_back(a);
        }
        return sen;
    }
};