Why memoization works, but returns false value from unordered_map
Please change bool --> int
Now it outputs:
countConstruct(ab, {ab, a, b}) = 2
Final code:
#include <string>
#include <unordered_map>
#include <iostream>
#include <vector>
using namespace std;
unordered_map<string, int> memo;
int countConstruct(const string& target, const vector<string>& wordBank)
{
if (target.size() == 0)
{
return 1;
}
if (memo.find(target) != memo.end())
{
return memo[target];
}
int totalCount = 0;
for (int i = 0; i < wordBank.size(); ++i)
{
if (wordBank[i].size() <= target.size())
{
string prefix = target.substr(0, wordBank[i].size());
if (prefix == wordBank[i])
{
totalCount = totalCount + countConstruct(target.substr(wordBank[i].size()), wordBank);
}
}
}
return memo[target] = totalCount;
}
int main()
{
// int c = countConstruct("purple", vector<string>({"purp", "p", "ur", "le", "purpl"}));
// int d = memo["purple"];
// memo.clear();
// cout << "countConstruct(purple, {purp, p, ur, le, purpl}) = " << countConstruct("purple", vector<string>({"purp", "p", "ur", "le", "purpl"})) << '\n';
// memo.clear();
// cout << "countConstruct(abcdef, {ab, abc, cd, def, abcd}) = " << countConstruct("abcdef", vector<string>({"ab", "abc", "cd", "def", "abcd"})) << '\n';
// memo.clear();
// cout << "countConstruct(skateboard, {bo, rd, ate, t, ska, sk, boar}) = " << countConstruct("skateboard", vector<string>({"bo", "rd", "ate", "t", "ska", "sk", "boar"})) << '\n';
// memo.clear();
// cout << "countConstruct(enterapotentpot, {a, p, ent, enter, ot, o, t}) = " << countConstruct("enterapotentpot", vector<string>({"a", "p", "ent", "enter", "ot", "o", "t"})) << '\n';
// memo.clear();
// cout << "countConstruct(eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef, {e, ee, eee, eeee, eeeee, eeeeee}) = " << countConstruct("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", vector<string>({"e", "ee", "eee", "eeee", "eeeee", "eeeeee"})) << '\n';
// memo.clear();
cout << "countConstruct(ab, {ab, a, b}) = " << std::flush << countConstruct("ab", vector<string>({"ab", "a", "b"})) << "\n";
cout.flush();
memo.clear();
return 0;
}