lc139-word break

class Solution {
unordered_map res;
public:
bool wordBreak(string s, unordered_set& wordDict) {
map> mp;
for (auto word: wordDict) {
mp[word[0]].push_back(word);
}
res[“”] = true;
return helper(s, mp);
}
bool helper(string s, map>& wordDict) {
if (res.find(s) != res.end()) {
return res[s];
}
for (auto word:wordDict[s[0]]) {
if (s.substr(0, word.length()) == word) {
if (helper(s.substr(word.length()), wordDict)) {
res[s] = true;
return true;
}
}
}
res[s] = false;
return false;
}
};