solved "Word Break" I and II on LeetCode (DP is easy, but second part's backtracking in iterative way is a bit tricky - dirty hack on stack) http://oj.leetcode.com/problems/word-break/ *and* http://oj.leetcode.com/problems/word-break-ii/

word_break.cpp

class Solution {
public:
    // word break i
    bool wordBreak(string s, unordered_set<string> &dict) {
        if (dict.empty()) return false;
        int maxSize  = max_element(dict.begin(), dict.end(), sizeComp)->size();
        int wordSize = s.size();
        bool *dp     = new bool[wordSize+1];
        // init dp array
        for (int i=1; i<=wordSize; ++i) dp[i] = false;
        dp[0] = true;

        for (int i=1; i<=wordSize; ++i) {
            int jLimit = i-maxSize >=0 ? i-maxSize : 0;
            for (int j=i-1; j>=jLimit; --j) {
                if (dp[j] && dict.find(s.substr(j, i-j))!=dict.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        bool result = dp[wordSize];
        delete[] dp;
        return result;
    }
    
    // word break ii
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> result;
        if (dict.empty()) {
            return result;
        }
        int maxSize  = max_element(dict.begin(), dict.end(), sizeComp)->size();
        int wordSize = s.size();
        vector< vector<int> > dp;
        vector<int> dp_0; dp_0.push_back(-1);
        dp.push_back(dp_0);

        for (int i=1; i<=wordSize; ++i) {
            vector<int> v;
            int jLimit = i-maxSize >= 0 ? i-maxSize : 0;
            for (int j=i-1; j>=jLimit; --j) {
                if (!dp[j].empty() 
                    && dict.find(s.substr(j, i-j)) != dict.end()) {
                    v.push_back(j);
                }
            }
            dp.push_back(v);
        }

        // DFS by stack
        stack<int> traceStack;
        traceStack.push(wordSize);
        deque<int> delimiter;
        while (!traceStack.empty()) {
            int p = traceStack.top();
            traceStack.pop();
            if (p == 0) { // an path ended
                result.push_back(delimitStr(s, delimiter));
                if (traceStack.empty()) break;
                int tmpTop = traceStack.top();
                while (delimiter[0] != tmpTop) {
                    delimiter.pop_front();
                }
                traceStack.pop();
            }
            else {
                for (int i=0; i<dp[p].size(); ++i) {
                    if (i != 0) traceStack.push(p);
                    traceStack.push(dp[p][i]);
                }
                delimiter.push_front(p);
            }
        }
        return result;
    }
    
private:
    struct StrSizeComp {
        bool operator() (string i, string j) { return i.size()<j.size(); }
    } sizeComp;

    // used for word break ii for string output
    string delimitStr(const string& s, const deque<int>& delimiter) {
        string res = "";
        int prev = 0;
        for (deque<int>::const_iterator it=delimiter.begin(), end = delimiter.end()-1; 
            it!=end; 
            ++it) {
            res.append(s.substr(prev, *it-prev) + " ");
            prev = *it;
        }
        res.append(s.substr(prev, s.size()-prev));
        return res;
    }
};