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)