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".
思路：
这道题最开始因为unordered_set纠结了好久。后来突然不知怎么的就顿悟了，也不记得之前到底在纠结什么了...
因为做了Word Break II，这道题就照猫画虎的做了出来。开始我存储了单词到达每个位置时的起始位置，后来发现不用，只要记录能不能到达当前位置即可。
bool wordBreak(string s, unordered_set<string> &dict) {
if(dict.empty() || s.empty())
return false;
vector<bool> v(s.length() + , false); //不需要存储是哪些位置开始的单词到达了v[j] 只要记录到没到就可以了
v[] = true;
for(int i = ; i <= s.length(); i++) //每一个单词的结束的下一个位置
{
for(int j = ; j < i; j++)//每个单词开始的位置
{
if(v[j] && dict.find(s.substr(j, i - j)) != dict.end()) //必须可以到达j 并且可以在字典中找到子串才置为真
{
v[i] = true;
break; //一旦为真就跳出本层判断 循环下一个结束位置
}
}
}
return v[s.length()];
}