We use a boolean vector dp[]. dp[** i**] is set to true if a valid word (word sequence) ends there. The optimization is to look from current position

**back and only substring and do dictionary look up in case the preceding position**

*i***with**

*j**dp[*is found.

**j**] == true```
bool wordBreak(string s, unordered_set<string> &dict) {
if(dict.size()==0) return false;
vector<bool> dp(s.size()+1,false);
dp[0]=true;
for(int i=1;i<=s.size();i++)
{
for(int j=i-1;j>=0;j--)
{
if(dp[j])
{
string word = s.substr(j,i-j);
if(dict.find(word)!= dict.end())
{
dp[i]=true;
break; //next i
}
}
}
}
return dp[s.size()];
}
```