leecode 解题总结：139. Word Break

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <unordered_map>using namespace std;/*问题:Given a non-empty string s and a dictionary WordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.You may assume the dictionary does not contain duplicate words.For example, givens = "leetcode",dict = ["leet", "code"].Return true because "leetcode" can be segmented as "leet code".分析:给定一个非空字符串，确定是否可以将字符串分割为多个字符串之后，且每个字符串都在字典中。字符串的切分应该是一个回溯的分割，一种暴力破解就是：采用回溯，得到分割结果，遍历结果中每一个字符串，看其是否在字典中。时间复杂度应该是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 c输出:truefalsetrue报错;超时"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]估计应该是可以用dp来做。设dp[i]表示s[0....i]是否可以通过划分使得所有划分的字符串在字典中dp[j]=dp[i] && s[i+1...j] in dict，其中 0 <= i <j那么所求目标为dp[n-1]初始dp默认为false关键:1 设dp[i]表示s[0....i]是否可以通过划分使得所有划分的字符串在字典中dp[j]=dp[i] && s[i+1...j] in dict，其中 0 <= i <j主要是将前面半段先做好，后面部分字符串直接查找2//dp[j]=dp[i-1] && s[i...j] in dict，其中0 <= i <=j, 0<= j < nfor(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())*/class Solution {public:    bool wordBreak(string s, vector<string>& wordDict) {		if(s.empty() || wordDict.empty())		{			return false;		}		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		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;						break;					}				}				else				{					if(dict.find(str) != dict.end())					{						dp.at(j) = true;						break;					}				}			}		}		bool isOk = dp.at(len - 1);		return isOk;    }};void PRocess(){	 vector<string> nums;	 string str;	 string value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num >> str )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 bool isOk = solution.wordBreak(str , nums);		 if(isOk)		 {			 cout << "true" << endl;		 }		 else		 {			 cout << "false" << endl;		 }	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}