Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given s = “leetcode”, dict = [“leet”, “code”].
Return true because “leetcode” can be segmented as “leet code”.
记得最开始做动态规划的题时是打开过这道题的，但是那时没什么思路。现在动态规划的题刷了不少了，今天再做这道题时很快就想出了状态和状态转移方程，不能不说还是有点进步。 定义A[i]表示0到下标为i的子字符能否被分割成dict中的多个单词。 那么A[i]与A[j],0<=j< i都有关系，，即A[i]与前A[]中的前i-1项都有关系，具体为：
如果A[0]为1，判断s中下标从1开始到i结束的字符是否在dict中，如果在，设置A[i]为1，跳出，否则进入第二步；如果A[1]为1，判断s中下标从2开始到i结束的字符是否在dict中，如果在，设置A[i]为1，跳出，否则进入第二步； ….. 这样一直遍历到A[i-1]位置。 在上面的遍历过程中如果遍历到某一步j,A[j]=1并且j+1到i表示的字符串出现在dict中，表示前j个字符串能分割成dict中的单词，j+1到i中的字符串串也能分割成dict中的单词，这样表示前i个字符能被分割成dict中的单词。
实际编写代码时，j可以从i开始倒着开始遍历，这样可以减少遍历的次数。
runtime:4ms
class Solution {public:bool wordBreak(string s, unordered_set<string>& wordDict) {int length=s.size();int *A=new int[length]();for(int i=0;i<length;i++){for(int j=i;j>=0;j–){if(j==i){A[i]=isExist(s,0,i,wordDict);}else if(A[j]==1){A[i]=isExist(s,j+1,i,wordDict);}if(A[i]==1)break;}}return A[length-1]==1;}int isExist(string &s,int first,int last,unordered_set<string> &wordDict){string str=s.substr(first,last-first+1);if(wordDict.count(str))return 1;;}};
一直有记日记的习惯，可是，旅行回来，
