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

Question

I have implemented a solution to this Cracking the Coding Interview question:

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. USE character array to perform this operation in place.

public static String conversion(String str, int length){

    char[] strChars = str.toCharArray();
    int numSpaces = 0;

    for(int i = 0; i < length; i++){
        if(strChars[i] == ' ')
            numSpaces++;
    }

    int newLength = length + 2 * numSpaces;
    char[] newChars = new char[newLength];

    for(int i = length - 1; i >= 0; i--){
        char c = strChars[i];
        if(c != ' '){
            newChars[i + 2 * numSpaces] = c;
        }
        else{
            newChars[i + 2 * numSpaces] = '0';
            newChars[i + 2 * numSpaces - 1] = '2';
            newChars[i + 2 * numSpaces - 2] = '%';
            numSpaces--;
        }
    }
    String newString = String.valueOf(newChars);
    return newString;
}

Can anyone give me any feedback on my implementation in regards of efficiency or improvements?

Answer 1

Your strategy of counting the spaces and then back-looping to shift the characters right (and replace spaces with %20) is good. The basic algorithm is probably as good as it gets as a character array system.

Your variable names are decent, and the code flows well.

On the other hand, there are some small things I would change.

Possible bug

Your code, given the input conversion("abc ", 3) you would output "abc" but you should not remove any "extra" padding in the string, you should return "abc "

In fact, you should only really have the one char[] array. The second one is making you do bad things ;-)

Enhanced fors

Use enhanced-for loops when possible, and always use {} blocks for if-statements, even 1-liners:

for(int i = 0; i < length; i++){
    if(strChars[i] == ' ')
        numSpaces++;
}

should be:

for (char c : strChars) {
    if (c == ' ') {
        numSpaces++;
    }
}

Comments

Comment unusual loops - your second for-loop is an odd one, and it often helps the reader if you comment why a loop is non-sequential (or even if you just make sure they are aware of it).

multiple indexes

Have you considered having a separate index for each position in the array - the position of the source character, and the position of where to insert it?

public static String conversion(String str, int length){

    char[] strChars = str.toCharArray();

    int numSpaces = 0;
    for (int i = 0; i < length; i++) {
        if(strChars[i] == ' ') {
            numSpaces++;
        }
    }

    int insert = length + 2 * numSpaces - 1;

    // loop backwards through source characters.
    for (int i = length - 1; i >= 0; i--) {
        char c = strChars[i];
        if (c == ' '){
            strChars[insert--] = '0';
            strChars[insert--] = '2';
            strChars[insert--] = '%';
        } else {
            strChars[insert--] = c;
        }
    }
    return String.valueOf(strChars);
}

The benefit of two indexes is that you can keep the logic more readable ... ("more" is relative) as each index moves by one character at a time... and a space counts as 3 characters.

Answer 2

You have re-invented the wheel which makes for a rather poor answer to an interview question (Academic context would be different). A good interview answer emphasises knowledge of the inbuilt capabilities balanced with an appreciation of development priorities. Simple code that uses inbuilt libraries is quick to code, robust, widely understandable and maintainable. I would expect to see something like:

log.info(new String("/A A/B B/C C").replaceAll(" ", "%20"));

Even better would be the following proving an appreciation of Test driven development:

@Test
public void test() {
    final String actualResult = new String("/A /B /C /D ").replaceAll(" ", "%20");
    assertEquals("/A%20/B%20/C%20/D%20", actualResult);
}

Otherwise your coding practice is reasonable.

• You have used Java naming conventions. +1
• You have mostly named for the problem domain. +1
• Your code is readable. +1

Expanding on Interview aspect The ability to stick closely to the requirements is an important skill in a developer but should not mean blindly following them. The specification is a reflection of requirements. Requirements shouldn't specify implementation details and may be in error. Spotting bogus things and having the strength of character to call them out in a constructive manner are important skills in a developer. A skilled interviewer can also use coding questions to test your reaction and behaviour as well as your technical/coding skills. As an interviewer I will often ask the impossible or unreasonable question. It is not there to trick you or catch you out, it is to test how you will react to something you will encounter in reality.

Answer 3

How come nobody notices the name of the method conversion() ? Shouldn't your method names be verbs? convert() is a better method name in this case.

Answer 4

You ignored the instructions

According to the problem statement, the String passed in has enough room to hold all the expanded characters, and you are supposed to do the expansion in-place. You went ahead and allocated a second character array and copied the characters from one array to another.

The whole backwards loop you used only makes sense if you are expanding in-place in the same array. If you allocate a new array, you might as well write the loop in the forwards direction since it doesn't make any difference.

Other things

1. I find it easier to read an if-else statement if the if condition is written in the positive sense if (c == ' ') rather than if (c != ' ').
2. Although your backwards loop does the right thing, I had to stare at it for a long time to convince myself that it was correct. Instead of an expression for the insertion point, I would just use another index.

(I just noticed that @rolfl already covered these points)

Rewrite

Here is how I would have modified your function. (It looks a lot like @rolfl's version actually):

public static String conversion(String str, int length)
{
    char[] strChars  = str.toCharArray();
    int    numSpaces = 0;

    for (int i = 0; i < length; i++) {
        if (strChars[i] == ' ') {
            numSpaces++;
        }
    }

    int newLength = length + 2 * numSpaces;

    for (int i = length - 1, j = newLength - 1; i >= 0; i--) {
        char c = strChars[i];
        if (c == ' ') {
            strChars[j--] = '0';
            strChars[j--] = '2';
            strChars[j--] = '%';
        } else {
            strChars[j--] = c;
        }
    }

    return String.valueOf(strChars);
}

Answer 5

How to split a string in Java

A tad bit on the concerned side here as I am not sure if your goal is a brute force coding requirement or not but the above link shows how to use the string split function an example is

String[] out = string.split("-");

Then just reassemble the string from out[]