The following program countConstruct should return the number of possible way the target string can be constructed from the given wordBank. Now, the memo object seem to store the correct value for "ab" which is 2, but it prints out 1. I just cannot figure out, what am I keep missing here over and over again. I appreciate anyone who can enlighten me about my failiure. Thank you.

#include <string>
#include <unordered_map>
#include <iostream>
#include <vector>

using namespace std;

unordered_map<string, int> memo;

bool 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;
}

CodePudding user response：

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;
}