LeetCode: Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

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

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

---

DFS can be used for this problem. We can start from the first letter of the string and find if current substring is a word is in the dictionary.

C++ Code:

/*
 * func: word_break_helper
 * goal: dfs helper function for word_break
 * @param s: input string s
 * @param start: start searching index
 * @param sentence: current sentence
 * @param dict: input word dict
 * @param result: final result set
 * return:
 */
void word_break_helper(string s, int start, string &sentence, unordered_set<string> &dict, vector<string> &result){
    if(start < 0){
        result.emplace_back(sentence.substr(1));
        return;
    }
    for(int i = start; i >= 0; --i){
        string tmp_word = s.substr(i, start - i + 1);
        size_t curr_length = sentence.length();
        if(dict.find(tmp_word) != dict.end()){
            sentence.insert(0, " " + tmp_word);
            word_break_helper(s, i-1, sentence, dict, result);
            sentence = sentence.substr(sentence.length() - curr_length);
        }
    }
}

/*
 * func: word_break
 * goal: return all possible sentences that can be constructed from the input string and dict
 * @param s: input string
 * @param dict: input dict
 * return: all possible sentences
 */
vector<string> word_break(string s, unordered_set<string> &dict){
    vector<string> result;
    if(s.length() == 0 || dict.size() == 0){
        return result;
    }
    string sentence = "";
    word_break_helper(s, s.length()-1, sentence, dict, result);
    return result;
}

Python Code:

# func: eturn all possible sentences that can be constructed from the input string and dict
# @param s: input string
# @param dict: input dict
# @return: all possible sentences
def word_break(s, dict):
    if not s or not dict:
        return []
    result = []

    def word_break_helper(start, sentence):
        if start < 0:
            result.append(sentence[1:])
            return

        for i in xrange(start, -1, -1):
            tmp_word = s[i:start+1]
            if tmp_word in dict:
                next_sentence = ' ' + tmp_word + sentence
                word_break_helper(i-1, next_sentence[:])

    word_break_helper(len(s)-1, '')
    return result

The test cases for this problem is not so fair. The first time, I did the dfs from 0 and it told me time limit exceed. But when I changed the start to the last letter in the string, it will pass.