concise C++ solution


  • 0

    class Solution {
    public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
    int ss = s.length();
    vector<string> res;
    vector<bool> record(ss + 1, false);
    record[0] = true;
    for(int i = 1; i <= ss; ++i){
    for(int j = i -1; j >= 0; --j){
    if(record[j] && wordDict.find(s.substr(j, i - j)) != wordDict.end()){
    record[i] = true;
    break;
    }
    }
    }
    if(record[ss] == true){
    string temp = "";
    word_break(s, wordDict, res, 0, temp);
    }
    return res;
    }
    void word_break(string s, unordered_set<string>& wordDict, vector<string>& res, int start, string temp){
    if(start == s.length()){
    temp.erase(temp.end() - 1);
    res.push_back(temp);
    return;
    }
    int i = start;
    for(; i < s.length(); ++i){
    string cur = s.substr(start, i - start + 1);
    if(wordDict.find(cur) != wordDict.end()){
    word_break(s, wordDict, res, i + 1, temp + cur + " ");
    }
    }
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.