leecode 解题总结：140. Word Break II

#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"].分析:给定一个非空字符串，确定是否可以将字符串分割为多个字符串之后，且每个字符串都在字典中。字符串的切分应该是一个回溯的分割，一种暴力破解就是：采用回溯，得到分割结果，遍历结果中每一个字符串，看其是否在字典中。时间复杂度应该是O(2^n)。关键就是回溯的过程是怎么样的，大致应该是: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(字符串个数) leetcodeleet code2 leecodeleet code3 abca b c5 catsanddogcat cats and sand dog输出:leet code空a b ccats and dog, cat sand dog又超时了，难道还是用之前的dp来做。因为dp标记了dp[i]表示s[0...i]可以被划分那么所有的结果应该是找到所有dp[i] = true的地方，然后但是之前dp[i]即使为true并没有说明s[0...i]具体应该是怎么划分，即没有存储使得dp[j] = dp[i-1] && s[i...j] in dict中的dp[i-1]应当需要保存下来，而且如果有多个，每一个都需要记录也就是要记录dp[i-1]中的位置i-1,作为上一个字符串的结尾位置如何存储?建立一个映射map<int , vector<int>>表明dp[j]可以通过dp[i-1]获得，如果dp[j]还可以由其他dp[k]获得，那么就把i-1,k等这样的全部存入到j对应的数组中那么该map中最后一个元素应该是n-1(假设字符串长度为n)n-1推得能够到达dp[n-1]的其他元素，从其他元素再得到更前面的元素，逆推，即可存储在路径数组中，遍历每个路径数组做切分即可关键:1 回溯超时，回溯其实是对每个位置尝试进行分割，时间复杂度为O(2^n)。用dp，设置一个双重循环，时间复杂度为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遍历，传入当前位置index，看能否找到使得该位置分割成功的之前所有位置，对每个位置递归查找，直到找到位置-1，存储一个完整路径，将所有路径存储后，然后切分*/class Solution {public:	//逆推获得路径数组，这个应该是要遍历的。这是递归还是迭代的？好像是递归。最后一个元素指向的位置是-1，递归截止，表明	void getPaths(unordered_map<int , vector<int> >& currentToPRevious , int index,		vector< vector<int> >& paths ,vector<int>& path)	{		if(currentToPrevious.empty())		{			return ;		}		//找到的最后一个位置下标是-1，表明上一个字符串的是直接从字符串的前面部分截取而来的，这里停止递归，将路径放入结果集		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);			//对每个位置递归查找			//将当前位置插入到位置数组中			//-1不要插入,终止，直接输出结果并检查下一个元素			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;//当前位置到上一个位置		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;						//如果已经存储了位置，则压入新的结果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到当前位置可以直接获得，存储位置为-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>();		}		//逆推获得路径数组		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();		//如果到达末尾，说明得到结果,返回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);			//左半部分在字典中，才继续递归处理			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);		//拼接结果		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;    }*/