Understanding LCS problem using recursion and memorization-CodePudding

SO, I am trying to solve LCS using Recursion memorization.
I know dp is more efficient but just for understanding, I wanted to solve using hashmap.

APPROACH -> There are 2 strings given s1 and s2 with lengths are x, and y.
In normal recursion we do something like this.

if (x==-1 || y==-1) return 0;
if (s1[x] == s2[y]) return 1 lcs(s1, s2, x-1, y-1);
else return max(lcs(s1, s2, x-1, y), lcs(s1, s2, x, y-1));

Now for implementing memorization, I will be using a hashmap
hashmap will be of string and int and the hashmap will be storing like this :
key -> to_string(x) "@@" to_string(y)
value -> the answer

I am using "@@" just to seperate those 2 numbers.

SO my code is ->:

int lcsRecursiveAndMemorization(std::string S1, std::string S2, std::unordered_map<std::string, int> &um, int x, int y)
{
    // if either string is empty 
    if (x == -1 || y == -1)
    {
        return 0;
    }

    // check if it is present already
    std::string temp = std::to_string(x)   "@@"   std::to_string(y);
    if (um.find(temp) != um.end())
    {
        return um[temp];
    }
    else
    {
        // check for if both the characters are equal
        if (S1[x] == S2[y])
        {
            // after getting answer store it and then return it.
            std::string temp1 = std::to_string(x - 1)   "@@"   std::to_string(y - 1);
            um[temp1] = 1   lcsRecursiveAndMemorization(S1, S2, um, x - 1, y - 1);
            return um[temp1];
        }
        else
        {
            // store answer for all the cases i.e.,
            // for x-1, y and x, y-1
            // and for x, y also
            std::string temp2 = std::to_string(x - 1)   "@@"   std::to_string(y);
            std::string temp3 = std::to_string(x)   "@@"   std::to_string(y - 1);

            int first_ = lcsRecursiveAndMemorization(S1, S2, um, x - 1, y);
            int second_ = lcsRecursiveAndMemorization(S1, S2, um, x, y - 1);

            // storing
            um[temp2] = first_;
            um[temp3] = second_;
            um[temp] = std::max(first_, second_);
            return um[temp];
        }
    }
}

int main()
{
    std::string S2 = "pmjghexybyrgzczy";
    std::string S1 = "hafcdqbgncrcbihkd";
    int x = S1.size() - 1;
    int y = S2.size() - 1;

    std::unordered_map<std::string, int> um;
    cout << "The LCS length using recursion   memorization is -> " << lcsRecursiveAndMemorization(S1, S2, um, x, y) << "\n";
    return 0;
}

So what is the problem with this code?
For me it's looks just fine.
It gives correct answer for small string, but for large string the answer is wrong.
It behaves in undefined manner like for the above two string the correct answer is 4.
And my program gives 5, but... if we swap the s1 with s2 it gives the correct answer i.e., 4? How?
I mean this should not affect the answer if we swap the 2 stings.

I just changed the recursive code to recursion memorization using hashmap.
I don't know why its not working, I guess there is some logic problem.

CodePudding user response：

I did not check the logic of your code, but if you want to memorise the result associated to a pair of integer, why not use a 2D array (or vector if you wish) instead of a hash table? Of course it will look like DP, but maybe it's because it's the same thing :) If you really want to stick with a map, maybe at least use std::pair<int,int> as keys, and try to see if your results are different with std::map, as one possible reason your code might not work is that hash tables always come with a risk of collisions.

PS : the lines um[temp2] = first_; um[temp3] = second_; should not be useful, as you are already storing these results at the end of the calls to lcsRecursiveAndMemorization(S1, S2, um, x - 1, y) and lcsRecursiveAndMemorization(S1, S2, um, x, y - 1).

CodePudding user response：

Yes, indeed the logic was wrong.

The new code looks like this->

int lcsRecursiveAndMemorization(std::string S1, std::string S2, std::unordered_map<std::string, int> &um, int x, int y){
// if either string is empty 
if (x == -1 || y == -1)
{
    return 0;
}

// check if it is present already
std::string temp = std::to_string(x)   "@@"   std::to_string(y);
if (um.find(temp) != um.end())
{
    return um[temp];
}
else
{
    // check for if both the characters are equal
    if (S1[x] == S2[y])
    {
        // after getting answer store it and then return it.
        // std::string temp1 = std::to_string(x - 1)   "@@"   std::to_string(y - 1);
        um[temp] = 1   lcsRecursiveAndMemorization(S1, S2, um, x - 1, y - 1);
        return um[temp];
    }
    else
    {
        // store answer for all the cases i.e.,
        // for x-1, y and x, y-1
        // and for x, y also
        // std::string temp2 = std::to_string(x - 1)   "@@"   std::to_string(y);
        // std::string temp3 = std::to_string(x)   "@@"   std::to_string(y - 1);

        int first_ = lcsRecursiveAndMemorization(S1, S2, um, x - 1, y);
        int second_ = lcsRecursiveAndMemorization(S1, S2, um, x, y - 1);

        // storing
        // um[temp2] = first_;
        // um[temp3] = second_;
        um[temp] = std::max(first_, second_);
        return um[temp];
        // return  std::max(first_, second_);
    }
}}

The problem was in how the data was being stored
The string temp1, temp2, temp3 were useless.
We only need the string temp. cause each subproblem is returning the answer for the main problem.

The updated code is self explanatory.