Leetcode 140 Word Break II

题意：给定一个string以及一个wordDict,要求返回一个vector<string> ，这个vector中的string都是word Dict中的组合

Input: s = “catsanddog”, wordDict = [“cat”,“cats”,“and”,“sand”,“dog”]
Output: [“cats and dog”,“cat sand dog”]

想法：backtracking, 想象一下每一轮你要干什么，首先拿wordDict中的每个单词去填写，如果对不上号，你就填下一个单词直到最后填到单词末尾就结束了。

class Solution {
public:
    vector<string> ret;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        dfs(s, "", 0 , wordDict);
        return ret;
    }

    void dfs(string& s, string cur, int st, vector<string>& wordDict) {
        if (st == s.size()) {
            cur.pop_back();
            ret.push_back(cur);
        }
        
        for(auto word : wordDict) {
            if(st + word.size() <= s.size()) {
                if(word == s.substr(st, word.size())) {
                    string temp = cur;
                    cur += word;
                    cur += " ";
                    dfs(s, cur, st+word.size(), wordDict);
                    cur = temp;
                }
            }
        }
    }
};

时间复杂度是指数级别的，递归栈空间是O(n)