Word Break -- LeetCode 139

[Quesion]
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]
Dynamic Programming: using one array A[n] to store whether first n letters of string s form a word sequence in dictionary, and A[0]= true,  A[i+1] will be true if A[j] == true and substr(j, i-j+1) is also a word in dictionary (0<=j<=i). The time complexity is O(N^2), space complexity is O(N).

DFS: try each prefix in dictionary recursively. Use a status memo to trim recursion branches.

Suppose Trie is built upon the word dictionary, Trie can help to get A[] initialized faster.

[Solution]
// -- Dynamic Programming --
class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        vector<bool> res(s.size()+1, false);
        res[0]=true;
        for (int i=0; i<s.size(); i++)
            for (int j=i; j>=0; j--)     //-- faster than moving forward --
                if (res[j] && wordDict.count(s.substr(j,i-j+1)) ) {
                    res[i+1] = true;
                    break;
                }
        return res.back();
    }
};

// -- DFS --
class Solution {
    unordered_set<string> seen; // -- to record failed branches
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if (wordDict.count(s)) return true;
        for (int i=0; i<s.size(); i++) {
            if (wordDict.count(s.substr(0,i+1)) ) {
                string ss = s.substr(i+1);
                if (seen.count(ss) ) continue;
                if (wordBreak(ss, wordDict))
                    return true;
                else seen.insert(ss);
            }
        }
        return false;
    }
};