#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <unordered_map>#include <sstream>using namespace std;/*問題:Given a non-empty string s and a dictionary WordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.Return all such possible sentences.For example, givens = "catsanddog",dict = ["cat", "cats", "and", "sand", "dog"].A solution is ["cats and dog", "cat sand dog"].分析:給定一個非空字符串，確定是否可以將字符串分割為多個字符串之后，且每個字符串都在字典中。字符串的切分應(yīng)該是一個回溯的分割，一種暴力破解就是：采用回溯，得到分割結(jié)果，遍歷結(jié)果中每一個字符串，看其是否在字典中。時間復(fù)雜度應(yīng)該是O(2^n)。關(guān)鍵就是回溯的過程是怎么樣的，大致應(yīng)該是:if(pos == len){   //遍歷分割后的每個字符串是否在字典中，如果都符合，就返回true；否則返回false}for(int i = beg ; i <= len ; i++){   //判斷左邊是否在里面   sub = s.substr(i , i - beg + 1);   if(sub 在字典中)   {      result.push_back(sub);      backTrace(i+1 , s)	  //彈出之前壓入的	  result.pop_back();   }}輸入:2(字符串個數(shù)) leetcodeleet code2 leecodeleet code3 abca b c5 catsanddogcat cats and sand dog輸出:leet code空a b ccats and dog, cat sand dog又超時了，難道還是用之前的dp來做。因為dp標(biāo)記了dp[i]表示s[0...i]可以被劃分那么所有的結(jié)果應(yīng)該是找到所有dp[i] = true的地方，然后但是之前dp[i]即使為true并沒有說明s[0...i]具體應(yīng)該是怎么劃分，即沒有存儲使得dp[j] = dp[i-1] && s[i...j] in dict中的dp[i-1]應(yīng)當(dāng)需要保存下來，而且如果有多個，每一個都需要記錄也就是要記錄dp[i-1]中的位置i-1,作為上一個字符串的結(jié)尾位置如何存儲?建立一個映射map<int , vector<int>>表明dp[j]可以通過dp[i-1]獲得，如果dp[j]還可以由其他dp[k]獲得，那么就把i-1,k等這樣的全部存入到j(luò)對應(yīng)的數(shù)組中那么該map中最后一個元素應(yīng)該是n-1(假設(shè)字符串長度為n)n-1推得能夠到達(dá)dp[n-1]的其他元素，從其他元素再得到更前面的元素，逆推，即可存儲在路徑數(shù)組中，遍歷每個路徑數(shù)組做切分即可關(guān)鍵:1 回溯超時，回溯其實是對每個位置嘗試進(jìn)行分割，時間復(fù)雜度為O(2^n)。用dp，設(shè)置一個雙重循環(huán)，時間復(fù)雜度為O(n^2)2 還是用dp來做，dp[i]表示s[0..i]是可以被劃分成功的，dp[j] = dp[i-1] && s[i...j] in dict，建立一個映射map<int , vector<int>>存儲能夠使得j劃分成功的所有位置對map遍歷，傳入當(dāng)前位置index，看能否找到使得該位置分割成功的之前所有位置，對每個位置遞歸查找，直到找到位置-1，存儲一個完整路徑，將所有路徑存儲后，然后切分*/class Solution {public:	//逆推獲得路徑數(shù)組，這個應(yīng)該是要遍歷的。這是遞歸還是迭代的？好像是遞歸。最后一個元素指向的位置是-1，遞歸截止，表明	void getPaths(unordered_map<int , vector<int> >& currentToPRevious , int index,		vector< vector<int> >& paths ,vector<int>& path)	{		if(currentToPrevious.empty())		{			return ;		}		//找到的最后一個位置下標(biāo)是-1，表明上一個字符串的是直接從字符串的前面部分截取而來的，這里停止遞歸，將路徑放入結(jié)果集		if(-1 == index)		{			paths.push_back(path);			return;		}		//如果找不到最后一個元素，說明不能切分		if(currentToPrevious.find( index  ) == currentToPrevious.end())		{			return ;		}		vector<int> previousArr = currentToPrevious[ index ];		if(previousArr.empty())		{			return ;		}		int size = previousArr.size();		int previousPos = -1;		for(int i = 0 ; i < size ; i++)		{			previousPos = previousArr.at(i);			//對每個位置遞歸查找			//將當(dāng)前位置插入到位置數(shù)組中			//-1不要插入,終止，直接輸出結(jié)果并檢查下一個元素			if(-1 == previousPos)			{				paths.push_back(path);				continue;			}			path.push_back(previousPos);			getPaths(currentToPrevious , previousPos , paths , path);			path.pop_back();//回溯		}	}    vector<string> wordBreak(string s, vector<string>& wordDict) {		vector<string> result;		vector<vector <string> > results;		if(s.empty() || wordDict.empty())		{			return result;		}		unordered_map<string ,bool> dict;		int size = wordDict.size();		for(int i = 0 ; i < size ; i++)		{			dict[ wordDict.at(i) ] = true;		}		int len = s.length();		vector<bool> dp(len  , false);		string str;		//dp[j]=dp[i-1] && s[i...j] in dict，其中0 <= i <=j, 0<= j < n		unordered_map<int , vector<int> > currentToPrevious;//當(dāng)前位置到上一個位置		for(int j = 0 ; j < len ; j++)		{			for(int i = 0 ; i <= j ; i++)			{				str = s.substr(i , j - i + 1); 				if(i)				{					if(dp.at(i-1) && dict.find(str) != dict.end())					{						dp.at(j) = true;						//如果已經(jīng)存儲了位置，則壓入新的結(jié)果i-1						if( currentToPrevious.find(j) != currentToPrevious.end() )						{							currentToPrevious[j].push_back(i-1);						}						else						{							vector<int> poss;							poss.push_back(i-1);							currentToPrevious[j] = poss;						}					}				}				else				{					//如果從0到當(dāng)前位置可以直接獲得，存儲位置為-1					if(dict.find(str) != dict.end())					{						dp.at(j) = true;						if( currentToPrevious.find(-1) != currentToPrevious.end() )						{							currentToPrevious[j].push_back(i-1);						}						else						{							vector<int> poss;							poss.push_back(-1);							currentToPrevious[j] = poss;						}					}				}			}		}		bool isOk = dp.at(len - 1);		if(!isOk)		{			return vector<string>();		}		//逆推獲得路徑數(shù)組		vector<vector<int> > paths;		vector<int> path;		path.push_back(len - 1);		//插入最后一個位置		getPaths(currentToPrevious , len - 1 , paths , path);		//切分字符串		result.clear();		if(paths.empty())		{			return result;		}				size = paths.size();		for(int i = 0 ; i < size ; i++)		{			len = paths.at(i).size();			stringstream stream;			//獲得的路徑是逆序的，必須逆置一下			reverse(paths.at(i).begin() , paths.at(i).end());			for(int j = 0 ; j < len ; j++)			{				if(j)				{					str = s.substr( paths.at(i).at(j-1) + 1 , paths.at(i).at(j) - paths.at(i).at(j-1) );					stream << " " << str;				}				else				{					str = s.substr(0, paths.at(i).at(j) + 1);					stream << str;				}			}			result.push_back(stream.str());		}		return result;    }};void print(vector<string>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size; i++)	{		cout << result.at(i) << ",";	}	cout << endl;}void process(){	 vector<string> nums;	 string str;	 string value;	 int num;	 Solution solution;	 vector<string> result;	 while(cin >> num >> str )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 result = solution.wordBreak(str , nums);		 print(result);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}/*	void backTrace(string& s , int beg , vector<string>& result, unordered_map<string , bool>& dict,		vector<vector <string> >& results)	{		if(s.empty() || beg < 0)		{			return;		}		int len = s.length();		//如果到達(dá)末尾，說明得到結(jié)果,返回true		if(beg == s.length())		{			results.push_back(result);			return;		}		string str;		for(int i = beg ; i < len; i++)		{			str = s.substr(beg , i - beg + 1);			//左半部分在字典中，才繼續(xù)遞歸處理			if(dict.find(str) != dict.end())			{				result.push_back(str);				//如果回溯成功，直接返回				backTrace(s , i + 1 , result , dict ,results);				result.pop_back();			}		}	}    vector<string> wordBreak2(string s, vector<string>& wordDict) {		vector<string> result;		vector<vector <string> > results;		if(s.empty() || wordDict.empty())		{			return result;		}		unordered_map<string ,bool> dict;		int size = wordDict.size();		for(int i = 0 ; i < size ; i++)		{			dict[ wordDict.at(i) ] = true;		}		backTrace(s , 0 , result , dict , results);		//拼接結(jié)果		result.clear();		if(results.empty())		{			return result;		}		size = results.size();		int len;		for(int i = 0 ; i < size ; i++)		{			len = results.at(i).size();			stringstream stream;			for(int j = 0 ; j < len ; j++)			{				if(j)				{					stream << " " << results.at(i).at(j);				}				else				{					stream << results.at(i).at(j);				}			}			result.push_back(stream.str());		}		return result;    }*/