直接在leetcode上做的，牛客上把词典wordDict改成了哈希表，懒得改了，牛客上的就没写。
思路：
table[i][j]代表从字符串s的i到j位置([i,j])是否能为一个词典中的单词，为1表示可以，为0表示不行。
e.g.
s:pineapplepenapple
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
首先初始化table表，即初始化table[0][x]，在词典中找能令0~x成为字典中词的单词。
这里找到pine与pineapple，即初始化table[0][3]与table[0][8]为1。
初始化完成后开始建表
第一遍遍历i=0,即字符串从0开始，找到table[0][3]:pine与table[0][8]:pineapple
遍历过程中，根据遍历结果继续建表，比如找到table[0][3]后相当于肯定0~3位置是一个符合要求的单词了。
现在以3~s.size()-1为一个新串，在里面继续找单词，如现在找到table[0][3]了，则继续在applepenapple中找，与初始化
时一样，继续在词典wordDict中找，如现在找到apple,则令table[4][8]为1，如此循环下去直到建表完成。
测试样例中有个样例aaaaaaaaaaaa.....，一直超时，这是由于没有判断样例是否能拆分就开始拆分造成的结果。
因此先判断字符串能否拆分，判断很简单，只要遍历table[i][s.size()-1]是否全为0即可，如果全为0，说明无法拆分到s字符串的最后一个字母，应该返回空。
返回结果很简单，根据表，首先遍历table[0][i],找到table[0][3]=1了，则跳到table[4],在table[4][i]中找1。。。。直到table[j][i]中j=s.size(),则将结果输入到result。
总体来说
table[i][j]代表从i到j能否构成一个词，则我们只要把表格建好，表格代表了所有单词可能出现的情况。
然后从0开始，找到第一个单词，然后以第一个单词后面的串继续找下一个单词，直到最后。
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
vector<vector<int>> table;
table.resize(s.size());
for(int i=0;i<table.size();i++)
{
table[i].resize(s.size());
}
//初始化:
for(int i=0;i<wordDict.size();i++)
{
if(strstr(s.data(),wordDict[i].data())-s.data()==0)
{
int idx=wordDict[i].size();
table[0][idx-1]=1;
}
}
//建表
for(int i=0;i<table.size()-1;i++)
{
for(int j=0;j<table[i].size();j++)
{
if(table[i][j]==1)
{
if(j==table[i].size()-1)
continue;
string tmp=s.substr(j+1);
for(int k=0;k<wordDict.size();k++)
{
if(strstr(tmp.data(),wordDict[k].data())-tmp.data()==0)
{
int idx=wordDict[k].size();
table[j+1][j+idx]=1;
}
}
}
}
}
vector<string> result;
bool flag=false;
for(int i=0;i<table.size();i++)
{
if(table[i][s.size()-1]==1)
flag=true;
}
if(!flag)
return result;
//查表返回结果
for(int i=0;i<s.size();i++)
{
if(table[0][i]==1)
{
int idx=i+1;
string tmp=s.substr(0,idx);
fillCore(result,table,i+1,tmp,s,s.size());
}
}
return result;
}
private:
void fillCore(vector<string>& result,vector<vector<int>>& table,int start,string s,string& input,int length)
{
if(start==length)
result.push_back(s);
for(int i=start;i<length;i++)
{
if(table[start][i]==1)//pineapplepenapple
{
string tmp=s;
s=s+" "+input.substr(start,i-start+1);
fillCore(result,table,i+1,s,input,length);
s=tmp;
}
}
}
};