C: What's wrong with my reverse string function?

Question

Been solving leetcode puzzles and thought I solved this one pretty quickly, yet I am running into a strange error. My output is matching the expected output, so I have no idea why it's rejecting my solution based off the following test case.

char* reverseString(char* s) 
{
/* Sample input: "Hello"
   Sample output: "olleh"
*/

    char * reversed_string;
    char temp[1];
    int length = 0;
    int i;

    if(s == NULL)
        return NULL;

    length = strlen(s);

/* While string is not null, increment pointer */
    while(*s != NULL)
    {
        s = s + 1;
    }

/* Allocate reversed string based off length of original string */
reversed_string = malloc(length + 1);

/* Traverse backwards for length of string */
/* Copy each letter to temp */
/* Concatenate each letter to reversed_string */
    for(i = 0; i < length; i++)
    {
        s = s - 1;
        strncpy(temp, s, 1);
        strcat(reversed_string, temp);
    }

    reversed_string[length] = '\0';

/* Return reversed string */
    return reversed_string;
}

MOutput = My Output

EOutput = Expected Output

Input:   "?CZU.9Iw8G3K?fse,b7 m;0?f :`c9d!D'`Pem0'Du0;9i` 03F,: 7,oPw'T'5`1g!iwR5J71iJ\"f;r6L;qZaDGx?cvkS 8\"UY2u`YC P3CM y`4v 1q7P;Zd1.;:RA!oYh;!2W8xMfMx8W2!;hYo!AR:;.1dZ;P7q1 v4`y MC3P CY`u2YU\"8 Skvc?xGDaZq;L6r;f\"Ji17J5Rwi!g1`5'T'wPo,7 :,F30 `i9;0uD'0meP`'D!d9c`: f?0;Z 7b,esf?K3G8wI9.UmC?"

MOutput: "?CmU.9Iw8G3K?fse,b7 Z;0?f :`c9d!D'`Pem0'Du0;9i` 03F,: 7,oPw'T'5`1g!iwR5J71iJ"f;r6L;qZaDGx?cvkS 8"UY2u`YC P3CM y`4v 1q7P;Zd1.;:RA!oYh;!2W8xMfMx8W2!;hYo!AR:;.1dZ;P7q1 v4`y MC3P CY`u2YU"8 Skvc?xGDaZq;L6r;f"Ji17J5Rwi!g1`5'T'wPo,7 :,F30 `i9;0uD'0meP`'D!d9c`: f?0;m 7b,esf?K3G8wI9.UZC?"

EOutput: "?CmU.9Iw8G3K?fse,b7 Z;0?f :`c9d!D'`Pem0'Du0;9i` 03F,: 7,oPw'T'5`1g!iwR5J71iJ"f;r6L;qZaDGx?cvkS 8"UY2u`YC P3CM y`4v 1q7P;Zd1.;:RA!oYh;!2W8xMfMx8W2!;hYo!AR:;.1dZ;P7q1 v4`y MC3P CY`u2YU"8 Skvc?xGDaZq;L6r;f"Ji17J5Rwi!g1`5'T'wPo,7 :,F30 `i9;0uD'0meP`'D!d9c`: f?0;m 7b,esf?K3G8wI9.UZC?"

Anyone spot what might be wrong with my function? Is there undefined behavior anywhere?

Change char temp[1] to char temp[2], as you need an additional entry for the null-character. — barak manos
– barak manos, Commented May 25, 2016 at 7:11
@barakmanos made the change and still breaks on that test case. Added a temp[1] = '\0'; after strncpy just to get it to compile. — MrPickles
– MrPickles, Commented May 25, 2016 at 7:15
You're right (in the comment to my (now deleted) answer). I didn't notice the n in strncpy. However, the following call to strcat is done with a non-null-terminated string, which is where the problem lies. — barak manos
– barak manos, Commented May 25, 2016 at 7:16

Rohan · Accepted Answer · 2016-05-25 07:16:56Z

1

You need to allocate 2 chars for temp and initialize with 0's, so change it to

char temp[2] = { 0 };

Also, initialize reversed_string after allocating memory to it, so that first strcat works properly.

reversed_string = malloc(length + 1);
reversed_string[0] = '\0';

answered May 25, 2016 at 7:16

Rohan

53.5k12 gold badges95 silver badges89 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

MrPickles Over a year ago

That was the problem. I didn't initialize reversed_string after I did the malloc and I just added the temp[2] per @barakmanos. Answer is accepted on leetcode now.

user3629249 · Accepted Answer · 2016-05-25 07:54:40Z

this part of the posted code:

for(i = 0; i < length; i++)
{
    s = s - 1;
    strncpy(temp, s, 1);
    strcat(reversed_string, temp);
}

is not doing the right thing.

It should be copying one byte at a time from the end of the original string to the beginning of the reversed string.

Suggest the following code which:

cleanly compiles
performs the desired functionality
is a complete program
because it is going to be used in one of the online coding contests does not perform any error checking.

and now, the code

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

// use meaningful variable and parameter names
char* reverseString(char* original)
{
    size_t length = strlen( original );


    /* Allocate reversed string based off length of original string */
    char *reversed = NULL;
    reversed = malloc(length + 1);

    char *dest = reversed;
    char *source = &(original[ strlen(original) -1 ]);

    for( ; source >= original; source--)
    {
        *dest = *source;
        dest++;
    }

    *dest = '\0';

    /* Return reversed string */
    return reversed;
} // end function: reverseString


int main( void )
{
    char inBuffer[ 4096 ];
    fgets( inBuffer, sizeof(inBuffer), stdin );

    // eliminate trailing newline if it exists
    char * newline = NULL;
    if( NULL != (newline = strstr( inBuffer, "\n" ) ) )
    {
        *newline = '\0';
    }

    char * newString = reverseString( inBuffer );
    printf( "%s\n\n", newString );
} // end function: main

Collectives™ on Stack Overflow

C: What's wrong with my reverse string function?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related