#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;}