Since we got a vector instead of a set, some people create a set out of the given vector. That is unnecessary since we are not going to add new elements to the set. We can simply **sort** the vector and do a binary search!

Here's the code in C++

```
class Solution {
public:
bool
wordBreak(string s, vector<string> &dict) {
vector<bool> dp(s.size()+1,false);
sort(dict.begin(), dict.end());
dp[0] = true;
for(int i = 1; i <= s.size(); ++i){
for(int j = 0; j < i; ++j){
if(dp[j]){
if(dp[i]) break;
dp[i] = std :: binary_search(dict.begin(), dict.end(), s.substr(j, i - j));
}
}
}
return dp[s.size()];
}
};
```