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".
思路：用所求值“——是否可以被分段，作为状态；string的每个字符为一个阶段。
class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { vector<bool> flag(s.length()+1, false); //indicate if until this position, words can be found in dictionary flag[0]=true; string str; for (int i = 0; i < s.length(); i++) { if(!flag[i]) continue; for(int l = 1; l <= s.length()-i;l++) { str = s.substr(i,l); if(dict.find(str)!=dict.end()) { flag[i+l] = true; } } } return flag[s.length()]; } };
原文：http://www.cnblogs.com/qionglouyuyu/p/4918289.html