Word Break II (Ladder)

Description

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.

Example
Gieve s = lintcode,
dict = ["de", "ding", "co", "code", "lint"].
A solution is ["lint code", "lint co de"].

Assumption

corner case, if empty dict, if no matching

Link

Lintcode_ladder

Method

1. backing tracking with memo string
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param s a string
     * @param wordDict a set of words
     */
    // Version 1, memo searching
    vector<string> wordBreak(string s, unordered_set<string> &wordDict) {
        // Write your code here
        unordered_map<string, vector<string>> combination;
        return helper(s, wordDict, combination);
    }
    vector<string> helper(string& s, unordered_set<string>& wordDict, unordered_map<string, vector<string>>& combination) {
        // if the s matches the wordDict
        if (combination.find(s) != combination.end()) {
            return combination[s];
        }
        vector<string> result;
        // if s empty() return empty
        if (s.empty()) {
            return result;
        }
        int len = s.size();
        for (int i = 1; i <= len; ++i) {
            string subString = s.substr(0, i);
            // cannot find in dict, try next 
            if (wordDict.find(subString) == wordDict.end()) {
                continue;
            }
            // can find in dict, but whole size of s
            if (i == len) {
                result.push_back(subString);
            } else {
            // test rest string, get all possible combination
                string suffix = s.substr(i);
                vector<string> tmp = helper(suffix, wordDict, combination);
                for (string item : tmp) {
                    item = subString + " " + item;
                    result.push_back(item);
                }
            } 
        }// for
        combination[s] = result;
        return result;
    }
};

Similar problems

x

Tags

Backtracking Dynamic Programming