theGreenCabbage theGreenCabbage - 1 month ago 8
Java Question

The value of length when replacing space with %20

I am working on a problem of replacing spaces with

%20
from Cracking the Coding Interview 5th edition:


Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place)


The algorithm I have is:

public static void replaceSpaces(String input, int length) {

char[] str = input.toCharArray();

int spaceCount = 0;
for(int i = length - 1; i >= 0; i--){
if(str[i] == ' ') {
spaceCount++;
}
}

int newLength = length + spaceCount * 2;

str[newLength] = '\0';

for(int i = length - 1; i >= 0; i--) {
if(str[i] == ' ') {
str[newLength - 1] = '0';
str[newLength - 2] = '2';
str[newLength - 3] = '%';
newLength = newLength - 3;
System.out.println(str);
} else {
str[newLength - 1] = str[i];
newLength = newLength - 1;
System.out.println(str);
}
}
}


Printing out each step of the function, here are my outputs:

Mr John Smith h
Mr John Smith th
Mr John Smith ith
Mr John Smithmith
Mr John SmitSmith
Mr John S%20Smith
Mr John n%20Smith
Mr Johnhn%20Smith
Mr Johohn%20Smith
Mr JoJohn%20Smith
Mr%20John%20Smith
Mr%20John%20Smith
Mr%20John%20Smith


I have two questions:


  1. We know the new length of the string is
    17
    . What I do not understand is, why we need to have
    [newLength - 1]
    instead of
    [newLength]
    . We are interested in replacing the current index, no? Or is it because the new length is 17, but when converted to indices, it's actually 16 (0th index).

  2. What is the purpose of:
    str[newLength] = '\0';


Answer

We don't all have that book, but from a pending edit, I see that the exact question is:

Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place)

From Cracking the Coding Interview 5th edition


So, it says that your input argument should be a char[].

Since you're changing the length of the text, your method would need to return the new length.


Question 1:

We know the new length of the string is 17. What I do not understand is, why we need to have [newLength - 1] instead of [newLength]. We are interested in replacing the current index, no? Or is it because the new length is 17, but when converted to indices, it's actually 16 (0th index).

You answered it yourself. With a length of 17, the indices are 0 to 16. If the array is only 17 long, accessing index 17 with throw an IndexOutOfBoundsException.


Question 2:

What is the purpose of: str[newLength] = '\0';

None whatsoever. It's is invalid and has no purpose in Java. Remove it.

Java Strings have a length(). In C, strings are zero-terminated, but not in Java.


To test the code, try running it with this:

char[] buffer = { 'M','r',' ','J','o','h','n',' ','S','m','i','t','h','*','*','*','*' };
int inLen = 13;
System.out.println("buffer: '" + new String(buffer) + "'");
System.out.println("inLen : " + inLen);
System.out.println("input : '" + new String(buffer, 0, inLen) + "'");
int outLen = replaceSpaces(buffer, inLen);
System.out.println("outLen: " + outLen);
System.out.println("result: '" + new String(buffer, 0, outLen) + "'");

Output should be:

buffer: 'Mr John Smith****'
inLen : 13
input : 'Mr John Smith'
outLen: 17
result: 'Mr%20John%20Smith'

Accessing input[17] in the method would throw IndexOutOfBoundsException.


Here is one possible implementation based on the shown code, that follows the quoted text, and stop processing once all spaces are replaced.

public static int replaceSpaces(char[] str, int length) {
    int spaceCount = 0;
    for (int i = length - 1; i >= 0; i--)
        if (str[i] == ' ')
            spaceCount++;
    int shift = spaceCount * 2;
    int newLength = length + shift;
    for (int i = newLength - 1; shift > 0; i--) {
        char c = str[i - shift];
        if (c != ' ') {
            str[i] = c;
        } else {
            str[i] = '0';
            str[--i] = '2';
            str[--i] = '%';
            shift -= 2;
        }
    }
    return newLength;
}

This produces the expected output from the test code above.