The following solution is by shibai86
Bottom up DP
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
int len = s.length();
vector<bool> dp(len + 1,false);
dp[len] = true;
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
string str = s.substr(i,j - i + 1);
if (dict.find(str) != dict.end() && dp[j + 1]) {
dp[i] = true;
break;
}
}
}
return dp[0];
}
};
edit: dp[i] has the boolean value that means if string[i : n] can be partitioned according to our dictionary. Hence dp[len] represents the empty string and dp[0] is the answer we are looking for.
For each iteration in the inner for loop, we add a new cut at index j to string[i : n], in whcih string[i : j] has never checked before but string[j + 1 : n](result is in dp[j + 1]) has been known since the previous
iteration in outer loop.