Array copy - Crash

Question

I am solving Leetcode problem #125 for checking if a stripped version of input string is a palindrome. What I mean by stripped is a string extracted from the original string and the extracted/stripped string contains only [a-z][0-9]

When the code under #0 is changed to #1, the program crashes with the error message. However when I replace it to #1 as shown below, the code gets accepted.

// https://leetcode.com/problems/valid-palindrome/

// Leetcode-125

// Helperfunction to find if a palindrome
bool isPal(char *s , int count)
{
    int iterations = (count/2)-1;
    
    for (int i = 0; i <= iterations; i++)
    {
        if (s[i] != s[count-1-i])
        {
            return false;
        }
    }
    return true;
}

// function that Leetcode's main calls.
bool isPalindrome(char * s) 
{
    int i = 0, j=0;
    int count = 0;
    
    if (!s)
        return false;
    
// Count number of valid characters. Replace invalid characters with 0xff.
// Change Upper to lower case numbers
    while (s[i] != '\0')
    {
    // [a-z][0-9]
        if ((s[i] >= '0' && s[i] <='9') ||
           (s[i] >= 'a' && s[i] <='z'))
           {
               count++;
           }
           else
           {
               if ((s[i] >= 'A' && s[i] <='Z'))
               {
                   count++;
                   s[i] = s[i] + ('a' - 'A');
               }
               else
               {
                   s[i] = 0xff;
               }
           }
           i++;
    }
    
    if (!count)
        return true;
           
    char *stripped = (char *) malloc ((count+1) * sizeof(char));
    i = 0;
#if 0  
// Enabling this causes a crash         
    while(s[i] != '\0')
    {
        if(s[i] != 0xff)
        {
            stripped[j] = s[i];
            j++;
        }
        i++;
    }
#else
    while(s[i] != '\0')
    {
        if ((s[i] >= '0' && s[i] <='9') ||
           (s[i] >= 'a' && s[i] <='z'))
           {
                stripped[j] = s[i];
                j++;
           }
           i++;
    }    
#endif

   stripped[count] = '\0';
    
    return isPal(stripped, count);
}

Fe2O3 · Answer

You're comparing a "signed char" with an "unsigned char".

Change this

if(s[i] != 0xff)

to this

if((unsigned char)s[i] != 0xff)

The clobbered signed characters will be promoted to 0xFFFF (32bit int) or 0xFFFFFFFF (64bit int), but the unsigned constant will be 0x00FF or 0x000000FF. Since they don't match, the code is copying EVERY character, even though some have not been counted... Overrunning the buffer that was allocated for fewer characters.

In the 'working' version, only valid (counted) characters are copied, so there is no buffer overrun.

You can narrow the region of differences between the two

    while(s[i] != '\0')
    {
#if 0 // Enabling this USED TO cause a crash         
        // if(s[i] != 0xff) // BAD, signed verses unsigned.
        if((unsigned char)s[i] != 0xff)
#else
        if((s[i] >= '0' && s[i] <='9') ||
           (s[i] >= 'a' && s[i] <='z'))
#endif
        {
            stripped[j] = s[i];
            j++;
        }
        i++;
    }
printf( "Debug: count(%d) i(%d) j(%d)
", count, i, j );
// We all KNOW 'j' will be less than 'count' if characters have been removed.
// "print debugging" is pretty sweet!

Beyond that, and apart from other efficiencies, I recommend using something like an ordinary 7-bit ASCII character '#' to clobber characters you want eliminated when you 'compact' down to "[0-9a-z]". Avoid the signed/unsigned problem altogther...

Bonus: Here's a slightly smaller version of the "helper" function. (Uppercase variable names for legibility.)

bool isPal( char *s , int count ) {
    for( int L=0, R=count - 1; s[L] == s[R]; L++, R-- )
        ; // just looping

    return L >= R;
}

And now, a Teaching Moment...

The objective is to compare only characters from a limited range, from both ends of a string. Based on 7-bit ASCII, a "look-up table" serves to not only validate in-/ex-clusion of characters, but also to convert (valid) uppercase alphabetic characters to lowercase. (No need for ctype.h function calls like isdigit() and tolower().)

Below, main() calls the function with a few sample strings, printing the results of the test. The function merely adjusts two indexes looking for valid characters, then compares two at a time. If the indexes meet in the middle then the string is palindromic.

#include  // all that is needed

int isPalindrome( const char *s ) {
    char *tbl =
        "................................................0123456789......"
        ".abcdefghijklmnopqrstuvwxyz......abcdefghijklmnopqrstuvwxyz.....";
    int L = 0, R = 0;

    while( s[R] ) R++; // poor boy's 'strlen(s)'. '\0' does not matter.

    do {
        while( L <= R && tbl[ s[L] ] == '.' ) L++;
        while( L <= R && tbl[ s[R] ] == '.' ) R--;
    } while( L <= R && tbl[s[L]] == tbl[s[R]] && (L+=1)>0 && (R-=1)>0 );
    return L > R;
}

int main() {
    char *strs[] = {
        "Abba",
        "LeVEl",
        "Levrel",
        "123Madam I'm    Adam321",
        "123Madam I'm  Q  Adam321",
    };

    for( int i = 0; i < sizeof strs/sizeof strs[0]; i++ )
        printf( "%s - '%s'
", isPalindrome( strs[i] ) ? "Yes" : "No ", strs[i] );

    return 0;
}

Output

Yes - 'Abba'
Yes - 'LeVEl'
No  - 'Levrel'
Yes - '123Madam I'm    Adam321'
No  - '123Madam I'm  Q  Adam321'

userRb221 · Answer

If we extract the "stripping" part of this problem out into a function, it can look like the following. I've used calloc to initialize the whole thing to zero so I don't have to manually null-terminate the resulting string. The new string will be allocated the same size as the original. I'm not worried about being as memory-miserly as possible.

char *strip(char *str) {
    char *result = calloc(0, strlen(str) + 1);
    
    if (!result) return NULL;

    for (char *it = result; *str; str++) {
        if ((*str >= 'a' && *str <= 'z') ||
            (*str >= 'A' && *str <= 'Z') ||
            (*str >= '0' && *str <= '9')) {
            *it++ = *str;
        }
    }

    return result;
}

Now, to check if the string is a palindrome, we'll operate on a stripped version of the input string, and get two pointers. One forward pointer that points to the beginning of the string, and one backward pointer that points to the end of the string.

We'll push these toward each other until they meet, checking each time to see if they are equal. If they aren't, we can free the stripped string we allocated with strip and return false.

If we reach the end of the loop that means the string is a palindrome and we can free the memory and return true.

bool isPalindrome(char *str) {
    if (!str) return false;

    char *stripped = strip(str);

    char *forward = stripped;
    char *backward = stripped + strlen(stripped) - 1;

    for (; forward <= backward; forward++, backward--) {
         if (tolower(*forward) != tolower(*backward)) {
             free(stripped);
             return false;
         }
    }

    free(stripped);

    return true;
}

Requires inclusion of , , , and .

Array copy - Crash

2 Answers