139. Word Break

https://leetcode.com/problems/word-break/

Solution:
1) Brute force DSF Recursion. But will cause TLE (not surprisingly);
2) DP. Suppose dp[i] represents the true status (can be separated into words) of substring from 0 to i, then dp[i+1] will be true if both dp[j] and wordDict.find(s.substr(j, i+1-j)) are true for 0<= j <i. Similar dp argument can also applied from right to left, and actually this one can be used to reduce the time complexity for the next question (II) (the details for the implementation will be a little bit different, see below. And also dp[i] now means the substring from i to n can be segmented).

Code:
DSF Recursion:

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if(s.empty()) return false;
        if(wordDict.find(s) != wordDict.end()) return true;
        for(int i=0; i<s.size(); ++i){
            string t = s.substr(0, i+1);
            if(wordDict.find(t)) != wordDict.end() && wordBreak(s.substr(i+1), wordDict)) return true;
        }
        return false;
    }
};

DP: from left to right

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int l = s.size();
        if(!l) return false;
        vector<bool> dp(l+1, false);
        dp[0] = true;
        for(int i=1; i<=s.size(); ++i){
            for(int j=0; j<i; ++j){
                if(wordDict.find(s.substr(j, i-j)) != wordDict.end() && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[l];
    }
};

DP: from right to left

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int l = s.size();
        if(!l) return false;
        vector<bool> dp(l+1, false);
        dp[l] = true;
        for(int i=l-1; i>=0; --i){
            for(int j=l; j>i; --j){
                if(wordDict.find(s.substr(i, j-i)) != wordDict.end() && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
};