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);
}
CodePudding user response：
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)\n", 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 <stdio.h> // 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'\n", 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'
CodePudding user response：
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 <string.h>, <ctype.h>, <stdbool.h>, and <stdlib.h>.