Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Solution:

class Solution {
public:
    // Recursive.
    bool recursive_wordBreakhelper(string s, int index, vector<string>& wordDict) {
        int size = s.size();
        bool ans;
        if (index == size) {
            return true;
        }
        for (int i = 0; i + index - 1 < size; i++) {
            string sub = s.substr(index, i);
            vector<string>::iterator it =
                find(wordDict.begin(), wordDict.end(), sub);
            if (it != wordDict.end()) {
                ans = recursive_wordBreakhelper(s, index + i, wordDict);
                if (ans) {
                    return true;
                }
            }
        }
        return false;
    }
 
    // Dynamic.
    bool wordBreakhelper(string s, vector<string>& wordDict) {
        vector<bool> ans(s.size() + 1, false);
        ans[0] = true;
        for (int i = 0; i < s.size(); i++) {
            for (int j = i; j >= 0; j--) {
                string sub = s.substr(j, i - j + 1);
                vector<string>::iterator it =
                        find(wordDict.begin(), wordDict.end(), sub);
                if (ans[j] && it != wordDict.end()) {
                    ans[i + 1] = true;
                }
            }
        }
        return ans[s.size()]; // since s is non-empty.
    }
 
    bool wordBreak(string s, vector<string>& wordDict) {
        return wordBreakhelper(s, wordDict);
    }
};

========== Another attempt  (DP) ========
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(), wordDict.end());
        int size = s.size();
        vector<bool> dp(size + 1, false);
        dp[0] = true;
     
        for (int i = 0; i < size; i++) {
            for (int j = i; j >= 0; j--) {
                string sbstr = s.substr(j, i - j + 1);
                if (st.count(sbstr) && dp[j]) {
                    dp[i+1] = true;
                }
            }
        }
        return dp[size];
    }
};

======== Another attempt (recursive with memorization) ====
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(), wordDict.end());
        unordered_map<string, bool> mp;
        return helper(s, 0, st, mp);
    }
   
    bool helper(string s, int idx, unordered_set<string>& st, unordered_map<string, bool>& mp){
        if (idx == s.size()) {
            return true;
        }
       
        string str = s.substr(idx);
        if (mp.count(str)) {
            return mp[str];
        }
       
        for (int i = idx; i < s.size(); i++) {
            string sb_str = s.substr(idx, i - idx + 1);
            if (st.count(sb_str)) {
                string str_remain = s.substr(i + 1);
                bool ans_exist = helper(s, i + 1, st, mp);
                mp[str_remain] = ans_exist;
                if (ans_exist) {
                    return true;
                }
            }
        }
        return false;
    }
};