word break

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”. 题解：这个题其实就是可以用动态规划来进行解决，简单来说：就是将字符串分为0~j和j~i， 其中范围 [0, j) 就是dp[j]，范围 [j, i) 就是s.substr(j, i-j)，其中dp[j]是之前的状态，我们已经算出来了，可以直接取，只需要在字典中查找s.substr(j, i-j)是否存在了，如果二者均为true，将dp[i]赋为true，并且break掉，此时就不需要再用j去分[0, i)范围了，因为[0, i)范围已经可以拆分了。最终我们返回dp数组的最后一个值，就是整个数组是否可以拆分的布尔值了。

bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.size();
        if(len == 0 || dict.size() == 0)
            return false;
        vector<bool> isright(len+1,false);//表示字符串s[0~i-1]是否可分的bool值
        isright[0] = true;//空串的情况
        //将字符串分为0~j,和j~i；然后不断递归细分，不断细分之后再从最小的开始判断，再恢复回来。类似于归并排序（去学算法里面的矩阵连乘）
        for(int i = 1;i <= len; i++)
        {
            for(int j = i-1; j >= 0; j--)
            {
                if(isright[j] && dict.find(s.substr(j,i-j))!= dict.end())//substr第二个参数表示有多少个
                {
                    isright[i] = true;//若可分，则当前位置设为true，
                    break;
                }
            }
        }
        return v[len];
    }