[dp] [dfs] [word break] [string] 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

word_break.cpp

// dp solution
bool word_break(const string& s, unordered_set<string>& dict) {
    if(s.empty() || dict.empty()) return true;
    vector<bool> dp(s.size()+1, false);  // <---- why define a 'dp' of length N+1? because dp[i] means whether a string of length i can be segmented using dict
    dp[0] = true; // cannot forget!
    for(int i=1; i<=s.size(); i++) {
        for(int j=0; j<i; j++) {        // looping j from 0 to i-1 seems better
            dp[i] = dp[j] && dict.find(s.substr(j+1, i-j)) != dict.end();
            if(dp[i] == true) break;
        }
    }
    return dp[s.size()];
}

// dfs
bool dfs(string s, unordered_set<string> &dict, int start_idx) {
	if(start_idx >= s.size()) return true;
	for(int j=start_idx; j<s.size(); j++) {
		string t = s.substr(start_idx, j-start_idx+1);
		if(dict.find(t) == dict.end()) continue;
		if(dfs(s, dict, j+1)) return true;
	}
    return false;
}
bool word_break(string s, unordered_set<string> &dict) {
    return dfs(s, dict, 0);
}