Replace all spaces in a string with “%20”

Write a method to replace all spaces in a string with ‘%20’.

My initial thoughts:

  1. Scan the string, if non-space, just copy, otherwise appending ‘%20’.

My initial codes:

public static String replaceSpace(String str) {
	String result = new String();
	for(int i = 0; i < str.length(); ++i) {
		result += str.charAt(i) == ' '? "%20" : str.charAt(i);
	}
	return result;
}

Comments after running:

  1. It works fine.
  2. Time/Space complexity O(n). An in-place replacement version is preferred.

Solution’s idea, my understandings:
This is a in-place solution. It works as follow:

  1. Count the number of space in the string
  2. Expand the size of the string to give spaces to the replacement
  3. Starting from the end of the new string, check the corresponding positions in the original string: if space, replace and move to the left 3 positions; otherwise, copy and move 1 position left.
	void replaceSpace(char* str) {
	char* ptr = str;
	int count = 0;
	int length = 0;
	while(*ptr) {
		if(*ptr == ' ')
			count++;
		length++;
	}
	int newLength = length + 2 * count;
	str[newLength] = '\0';
	
	for(int i = newLength - 1; i >= 0; --i) {
		if(str[i - 2 * count] == ' ') {
			str[i] = '0';
			str[i-1] = '2';
			str[i-2] = '%';
		} else {
			str[i] = str[i - 2 * count];
		}
	}
}

Problems:

  1. Highlighted while loop does not include an increment of the pointer, resulting in infinite loop.
  2. Highlighted if condition: if we need to replace the space, after doing that, we should offset the iterator a few positions to the left, other than decreasing 1, when needed if there’s no replacement.
  3. After one replacement, the ‘count’ should be decreased since the offset will be less.

Correctly working codes:

void replaceSpace(char* str) {
	char* ptr = str;
	int count = 0;
	int length = 0;
	while(*ptr) {
		if(*ptr == ' ')
			count++;
		length++;
		ptr++;
	}
	int newLength = length + 2 * count;
	str[newLength] = '\0';
	
	for(int i = newLength - 1; i >= 0; ) {
		if(str[i - 2 * count] == ' ') {
			str[i] = '0';
			str[i-1] = '2';
			str[i-2] = '%';
			i = i - 3;
			count--;
		} else {
			str[i] = str[i - 2 * count];
			--i;
		}
	}
}
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: