Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

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

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

First, I tried backtracking algorithm, but I met Time Limit Exceeded error.

Backtracking:o(n!)

//can I reuse the words in dict?
//What should I return if s is an empty string?
//s = abc wordDict = "abc" ? what should I return?

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        //extreme case
        if(s.size() == 0 || wordDict.empty() == true) return false;
        return _wordBreak(s, wordDict);
        
    }
    bool _wordBreak(string s, unordered_set<string>& wordDict){
        //base condition
        if(s.size() == 0) return true;
        
        //ordinary case
        for(size_t i = 0; i < s.size(); i++){
            if(wordDict.find(s.substr(0, i + 1)) != wordDict.end()){
                //s.substr is found in dict
                if(_wordBreak(s.substr(i + 1, -1), wordDict) == true){
                    return true;
                }
            }
        }
        return false;
    }
};

Dynamic programming: o(n^2)

dp[i] = dp[j – 1] && s.substr(j, i – j + 1), 0 <= j <= i

//can I reuse the words in dict?
//What should I return if s is an empty string?
//s = abc wordDict = "abc" ? what should I return?
//the time complexity of backtracking algorithm is unbearable o(n!)

//Dynamic programmming solution
//o(n^2)
class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        //extreme case
        if(s.size() == 0 || wordDict.empty() == true) return false;
        bool dp[s.size()];
        memset(dp, false, sizeof(dp));
        for(size_t i = 0; i < s.size(); i++){
            for(int j = i; j >= 0; j--){
                if(wordDict.find(s.substr(j, i - j + 1)) != wordDict.end()){
                    if(j == 0) dp[i] = true;
                    else if(dp[j - 1] == true) dp[i] = true;
                    
                }
            }
            
        }
        return dp[s.size() - 1];
    }
};