Word Break

Word break I:

s = "leetcode",
dict = ["leet", "code"].

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

Brute Force Solution (TLE)

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

Modified: use a vector<bool> as memo

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

Notes
Analysis of time complexity. What is the worst case?

word = "aaaaab"
dict = {"a", "aa", "aaa"}

http://blog.jobbole.com/60798/

Word Break II

Return the result:

s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

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

        vector<vector<string>> memo(n);
        for ( int i = 0; i <= n-1; i++ ) {
            if ( wordDict.find(s.substr(0, i+1)) != wordDict.end() ) memo[i].push_back(s.substr(0, i+1));
            for ( int j = i-1; j >= 0; j-- ) {
                if ( memo[j].size() == 0 ) continue;
                if ( wordDict.find(s.substr(j+1, i-j)) == wordDict.end() )  continue;
                int ntmp = memo[j].size();
                for ( int k = 0; k <= ntmp-1; k++ ) {
                    string stmp = memo[j][k] + " " + s.substr(j+1, i-j);
                    memo[i].push_back(stmp);
                }
            }
        }
        return memo[n-1];
    }
};

Notes
For each i <= n-1， use a vector of string to record the result up to i-th position.