题目描述

点这里

思路分析

线性dp+暴搜
$f[i]:[i,n]$能否被拆分
$[i,j]的hash存在andf[j+1]=truethenf[i]=truel$

代码实现

class Solution {
public:vector<bool> f;unordered_set<string> hash;vector<string> ans;int n;vector<string> wordBreak(string s, vector<string>& wordDict) {n=s.size();f.resize(n+1);for(auto t:wordDict) hash.insert(t);f[n]=true;for(int i=n-1;~i;i--){for(int j=i;j<n;j++){if(hash.count(s.substr(i,j-i+1))&&f[j+1]) f[i]=true;}}dfs(s,0,"");return ans;}void dfs(string &s,int u,string path){if(u==n){path.pop_back();ans.push_back(path);return;}for(int i=u;i<n;i++){if(hash.count(s.substr(u,i-u+1))&&f[i+1]){dfs(s,i+1,path+s.substr(u,i-u+1)+" ");}}}
};