[LeetCode] Word Break I

Problem Statement (link):

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".

Analysis:
This problem could be done naively using recursion - code given below in Sol 1. However, the time complexity is O(m^n) in worse case, where m is length of the string and n is length of the dictionary.

Obviously, the exponential solution is not optimal. We see this because the recursion has overlapped sub-problems.

Consider using DP. We construct a dp vector, where entry i represents whether s[0 : i-1] can be broke down to words in dictionary. Suppose dp[i-1] == true, dp[i] would be true iff:
1) string from index 0 to i is in dictionary, Or
2) for 0 <= j < i, if dp[j] == true, and string from index j to i is in dictionary

The index map is :

string s:         a a c d d a e
i or j:              0 1 2 3 4 5 6
dp index:    0 1 2 3 4 5 6 7

The time complexity of this DP algorithm is O(m*n), the space comlexity is O(m), where m is length of the string and n is length of the dictionary.

Code:
Sol 1 - Recursion:

bool wordBreak(string s, unordered_set<string> &dict) {
    return recur(s, dict, 0);
}
bool recur(string s, unordered_set<string> &dict, int st) {
    if (st==s.length()) return true;
    for(unordered_set<string>::iterator it=dict.begin(); it!=dict.end(); it++) {
        string t = *it;
        int len = t.length();
        if (st+len>s.length()) {
            continue;
        if (!s.substr(st, len).compare(t)) {
            if (recur(s, dict, st+len))
                return true;
        }
    }
    return false;
}

Sol 2 - DP

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