Word Break II

gistfile1.cpp

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        const int s_len = s.length();
        break_.resize(s_len);
        word_len_list_.resize(s_len);
        ori_str_ = &s;
        
        for (int i = 0; i < s_len; ++i) {
            for (const string& word : dict) {
                const int word_len = word.length();
                // Not long enough to match this word.
                if (i + 1 < word_len) continue;
                // Can't match s[0, i - word_len] and skip to compare the string below.
                if (i - word_len >= 0 && break_[i - word_len].size() == 0) continue;
                // s[i - word_len + 1, i] equal to word.
                // Think! How to make this faster?
                if (s.substr(i - word_len + 1, word_len) == word) {
                    break_[i].push_back(word_len);
                }
            }
        }
        
        vector<string> result;
        if (break_[s_len - 1].size() != 0) GenerateResult(s_len - 1, 0, &result);
        return result;
    }
    
private:
    void GenerateResult(int k, int word_num, vector<string>* result) {
        if (k < 0) {
            int start_pos = 0;
            string sentence;
            for (int i = word_num - 1; i >= 0; --i) {
                sentence += ori_str_->substr(start_pos, word_len_list_[i]);
                if (i != 0) sentence = sentence + " ";
                start_pos += word_len_list_[i];
            }
            result->push_back(sentence);
        } else {
            for (const int word_len : break_[k]) {
                word_len_list_[word_num] = word_len;
                GenerateResult(k - word_len, word_num + 1, result);
            }
        }
    }
    
    vector<vector<int>> break_;
    vector<int> word_len_list_;
    const string* ori_str_;  // Not owned.
};