Reverse a C-Style String

Write code to reverse a C-Style String. (C-String means that “abcd” is represented as five characters, including the null character.)

My initial thoughts:

  1. Swap the 1st with the last, then 2nd with the second last, etc
  2. If the size of string is n, then you need to swap (0,n-1), (1,n-2) …

My initial codes:

	public static String reverseCStyleString(String s) {
		char[] result = s.toArray();
		for (int i = 0; i < (s.length() - 1) / 2; ++i) {
			char temp = result[i];
			result[i] = result[s.length() - 1 - i];
			result[s.length() - 1 - i] = temp;
		}
		return new String(result) + "\0";
	}

Comments after running:

  1. Compiling error at highlighted line. It should be “toCharArray()”
  2. This is not going to handle C-Style string. The “” has no effect at all. I think I misunderstood this question. Or this question cannot even be written in Java.
  3. Nevertheless, it works for reversing the input string, with time complexity O(n/2), space complexity O(1).

Solution:

void reverse(char *str) {
	char * end = str;
	char tmp;
	if (str) {	// to handle empty string
		while (*end) {	// find the null character
			++end;
		}
		--end; // last meaningful element
		while (str < end) {	// terminal condition: 
							// str and end meets in the middle
			tmp = *str;	// normal swap subroutine
			*str++ = *end; // str advance one step
			*end-- = tmp;	// end back one step
		}
	}
}

Comments:

  1. This is purely C code.
  2. Handle boundary condition: when the string is empty.
  3. Time complexity O(n/2) and space complexity O(1).

When I tried to write that part of code again, I wrote:

void reverse(char * str)
{
	char *end = str;
	if(str) {
		while(*end) {
			++end;
		}
		--end;
		
		char *tmp;
		while(str < end) {
			*tmp = *str;
			*str++ = *end;
			*end-- = *tmp;
		}
	}
}

Almost identical to the solution except the highlighted line where I didn’t initialize tmp and then I try to de-reference it and I’ve got segmentation fault.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: