意甲冠军：推断字符串给定的字符串是否构成词典。

来推断目标字符串相匹配整个字典。我们需要来推断目标字符串的每个前缀开始的下一场比赛，这需要匹配目标字符串的成功，所有前缀的枚举。

class TrieNode{//from http://www.cnblogs.com/x1957/p/3492926.html

public:

    TrieNode* ch[26];//char指针数组

    bool isWord;

    TrieNode():isWord(false){

        memset(ch,0,sizeof(TrieNode*)*26);

    }

    void insert(const string& ps){

        TrieNode*q=this;

        int id;

        const char* p=ps.c_str();

        while(*p){

            id=p[0]-'a';

            if(NULL==q->ch[id])

                q->ch[id]=new TrieNode();

            q=q->ch[id];

            p++;

        }

        q->isWord=true;//是一个前缀

    }

    ~TrieNode(){

        for(int i=0;i<26;++i)

            delete ch[i];

    }

};

class Solution {

public:

    bool *find;

    TrieNode *root;

    void match(string &s,int st,int ed){

        TrieNode*p=root;

        for(int i=st;i<ed;++i){

            if(p->ch[s[i]-'a']){

                p=p->ch[s[i]-'a'];

                if(p->isWord)find[i]=true;

            }

            else break;

        }

    }

    bool wordBreak(string s, unordered_set<string> &dict) {

        int i,n=s.size();

        unordered_set<string>::iterator bg,ed;

        root=new TrieNode();

        for(bg=dict.begin(),ed=dict.end();bg!=ed;bg++){

            root->insert(*bg);

        }

        find=new bool[n];

        memset(find,0,sizeof(bool)*n);

        //先匹配前缀

        match(s,0,n);

        //再从全部匹配的单词開始接下去匹配

        for(i=0;i<n&&find[n-1]==false;++i)

            if(find[i])

                match(s,i+1,n);

        bool ans=find[n-1];

        delete[]find;

        delete root;

        return ans;

    }

};

DP版：

一个串AB可看成两个子串A、B构成。假设A和B都匹配。则AB匹配。用dp[i]表示前缀(0,i)是否匹配，则dp[n]=dp[0,k]&dp[k+1,n]，k∈[0,n]。

这里dp[0,k]比較easy求，要推断后缀dp[k+1,n]是否在dict中。除了通过set.find(dp[k+1,n])不知还有什么办法。

bool wordBreak(string s, unordered_set<string> &dict) {

        int i,j,n=s.size();

        bool *dp=new bool[s.size()];

	 	memset(dp,0,sizeof(bool)*n);

		for(i=0;i<n;++i){

			dp[i]=dict.find(s.substr(0,i+1))!=dict.end();

			for(j=0;j<i&&!dp[i];++j){

				dp[i]=(dp[j]&(dict.find(s.substr(j+1,i-j))!=dict.end()));

			}

		}

		bool ans=dp[n-1];

		delete[]dp;

		return ans;

    }

问题2：输出全部匹配的字符串 https://oj.leetcode.com/problems/word-break-ii/

方法：在每一个匹配的时候，针对每一个匹配的子串，记录能够匹配到该位置的子串起始位置。这样串中的一个字符就可能有多种匹配结果。

仅仅要由后往前回溯输出全部可能就可以。

class TrieNode{

public:

	TrieNode*child[26];

	bool isWord;

	TrieNode():isWord(false){

		memset(child,0,sizeof(TrieNode*)*26);

	}

	void insert(const string &str){

		int n=str.size(),i,id;

		TrieNode*p=this;

		for(i=0;i<n;++i){

			id= str[i]-'a';

			if(!p->child[id]) {

				p->child[id]=new TrieNode();

			}

			p=p->child[id];

		}

		p->isWord=true;

	}

	~TrieNode(){

		for(int i=0;i<26;++i){

			delete child[i];

			child[i]=NULL;

		}

	}

};

class Solution{

public:

	TrieNode*root;

	bool *find;

	vector<string>ans;

	void match(string &str,int st,int ed,vector<set<int> >&pos){

		int i,id;

		TrieNode*p=root;

		for(i=st;i<=ed;++i){

			id=str[i]-'a';

			if(p->child[id]){

				p=p->child[id];

				if(p->isWord){

					find[i]=true;

					pos[i].insert(st);

				}

			}

			else break;

		}

	}

	void dfs(string &str,int id,vector<set<int> >&pos,int *b,int len){

		if(id<0){

			string tmp;

			for(int i=len-1;i>0;--i){

				if(i<len-1)tmp+=" ";

				tmp+=str.substr(b[i],b[i-1]-b[i]);

			}

			ans.push_back(tmp);

			return;

		}

		set<int>::iterator bg=pos[id].begin(),ed=pos[id].end();

		for(;bg!=ed;bg++){

			b[len]=*bg;

			dfs(str,b[len]-1,pos,b,len+1);

		}

	}

	vector<string>wordBreak(string s, unordered_set<string>&dict){

		if(s.size()==0){

			return vector<string>();

		}

		unordered_set<string>::iterator bg,ed;

		root=new TrieNode();

		int n=s.size(),i;

		for(bg=dict.begin(),ed=dict.end();bg!=ed;bg++){

			root->insert(*bg);

		}

		find=new bool[n];

		vector<set<int> >pos(n);

		int *b=new int[n+2];

		memset(find,0,sizeof(bool)*n);

		match(s,0,n-1,pos);

		for(i=0;i<n;++i){

			if(find[i])

				match(s,i+1,n-1,pos);

		}

		int x=0;

	//	cout<<pos[6].size();

		if(find[n-1]){

			b[x++]=n;

			dfs(s,n-1,pos,b,x);

		}

		delete[] find;

		delete[] b;

		return ans;

	}

};