Magic Spells

  • + 0 comments

    If anyone is interested in a recursive solution to the second part :) :

        //Get spell and journal name
        string spellName = spell->revealScrollName();
        string journal = SpellJournal::journal;  
    
        // Initialize the memoization table with -1 (indicating uncomputed)
        int n = spellName.size();
        int m = journal.size();
        //memo is used to keep track of the computation, avoiding usless computation
        vector<vector<int>> memo(n + 1, vector<int>(m + 1, -1)); 
    
        auto f = [&spellName, &journal, &memo](int n, int m, auto& f) -> int {
            if (n == 0 || m == 0) return 0; //Reached the end of one string
            if (memo[n][m] != -1) return memo[n][m]; //If already computed
            
            if (spellName[n - 1] == journal[m - 1]) { //Update memo adding the new computation
                memo[n][m] = 1 + f(n - 1, m - 1, f);
            } else {
                memo[n][m] = std::max(f(n - 1, m, f), f(n, m - 1, f)); //Recall f over n-1 and m-1 to gety the substring which return the  highest value
            }
            return memo[n][m]; // Return the computed result
        };