CODEWITHSUNDEEP
cfree
Dave Xu
Dave Xu

Reputation: 147

Why free() impact other variable's value?

Practice for "Distinct Subsequences" online:

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

My code is listed below.

For test case {s="aaaaaaaaaaaaa", t="aa"}:

If I enable //free(pMtx); before final return, my codes will treated as failure with a result 79.

If I keep this free(pMtx); commented out, my result is correct 78.

Then I tried on my local PC, everything is fine with free(pMtx); enabled.

Therefore I'm really confused why this happens?

int numDistinct(char* s, char* t) {
    int slen=strlen(s);
    int tlen=strlen(t);
    if( (0 == slen) || (0 == tlen)||(tlen>slen))
        return 0;

    int* pMtx = (int*)malloc(slen*tlen*sizeof(int));

    for(int ss=0; ss<slen; ss++)
    {
        if(0==ss)
        {
            pMtx[0] = (s[0]==t[0]) ? 1 : 0;
            continue;
        }

        for(int tt=0; tt<tlen; tt++)
        {
            int cur = ss*tlen + tt;

            if(tt>ss)
            {
                pMtx[cur]=0;
                continue;
            }

            int v1 = (tt==0) ? 1 : pMtx[cur-tlen-1];
            int vv = v1 + pMtx[cur-tlen];

            if(s[ss]==t[tt])
                pMtx[cur] = (vv>=pMtx[cur-tlen]) ? vv : pMtx[cur-tlen];
            else
                pMtx[cur] = pMtx[cur-tlen];
        }
    }

    int rst = pMtx[slen*tlen-1];

    //free(pMtx);  //------------> open it will result in wrong rst value ???

    return rst;    
}

Upvotes: 1

Views: 107

Answers (1)

Klas Lindb&#228;ck
Klas Lindb&#228;ck

Reputation: 33283

The problem is here:

    if(0==ss)
    {
        pMtx[0] = (s[0]==t[0]) ? 1 : 0;
        continue;
    }

You need to initialize pMtx[0] to pMtx[tlen-1], not just the first element.

The first time you allocate memory, it is often zeroed out (because the OS may have done it before giving it to the process). When you free memory, it can get reused the next time you allocate memory and then it won't be zero anymore. So if you call this function more than once from main it explains why it fails.

Upvotes: 3

Related Questions