Replace ' ' Spaces in a URL with a '%20' - Coding Challenge

Question

This was a small coding challenge proposed at my school. The problem is:

Given a string (or URL), replace the white-spaces inside of the string with %20, but any spaces on the outside should not be included.

For example, input " Mr John Smith " would return "Mr%20John%20Smith".

I have completed this challenge successfully using the code below. My question is, is there any way to improve the efficiency? I believe the complexity is currently \$O(2n) = O(n)\$ given the 2 for loops. I do not want to use any libraries or functions like str.replace(). But I'm assuming there is a better way than trimming and then counting the whitespace.

public class URL {
 /**
 * @description URLify ~ A small method that makes a string with spaces URL Friendly!
 * @param str
 * @param length
 * @return String
 */
 public static String URLify(String str) {
 str = str.trim();
 int length = str.length();
 int trueL = length;
 if(str.contains(" ")) {
 for(int i = 0; i < length; i++) {
 if(str.charAt(i) == ' ') {
 trueL = trueL + 2;
 }
 }
 char[] oldArr = str.toCharArray();
 char[] newArr = new char[trueL];
 int x = 0;
 for(int i = 0; i < length; i++) {
 if(oldArr[i] == ' ') {
 newArr[x] = '%';
 newArr[x+1] = '2';
 newArr[x+2] = '0';
 x += 3;
 } else {
 newArr[x] = oldArr[i];
 x++;
 }
 }
 str = new String(newArr, 0, trueL);
 }
 return str;
 }
 public static void main(String[] args) {
 String str = " https://google.com/ testing .pdf ";
 str = URLify(str);
 System.out.print(str);
 }
}

Note: I am looking for any criticism. I would really like to improve my skills in general.

• holroy: Of course the ultimate solution is str.trim().replaceAll(" ", "%20"), but I guess that is kind of cheating?
• JollyJoker: @holroy One possible nitpick is that whitespace characters other than a normal space wouldn't be replaced.
• JollyJoker: Is the problem statement a direct copy? In particular, do you know if "whitespace" was intended to mean just the space character? @tommy
• fdomn-m: "I do not want to use any libraries or functions like str.replace()" but a library function like str.trim() is ok? 50% of the requirement is handled by a library function. Tip: be consistent.
• Tommy Yamakaitis: @JollyJoker It is not the direct problem statement. I meant just the space character. Sorry, I can see how that would be unclear.

Answer 1

Let me give some comments to your code as well, with a refactoring coming out at finally:

• Building a char array, seems to be wasteful – Why don't you use StringBuilder? I know when reinventing the wheel, there could be some debate as to what you are allowed to use or not. But you're already using str.trim() and str.toCharArray(), so why not StringBuilder?

• Try to avoid multiple repeated loops – In your code you loop it once to get the new length into the strangly named trueL, this should (if kept) be named newLength or similar. Repeating loops is considered expensive, and should be avoided, if possible.

• oldArr and newArr? – In general I don't think variable names including array, arr, table, and so on are good names. In most cases you know it's an array due to the presence of the array indexing braces. Maybe originalChars or strChars, could be better names.

• Good use of length = str.length() – I like that you calculate then length just once, and use that in the for loop.

• Choose appropriate loops – Albeit the charAt() is slightly faster, I think that in this case I would opt for the for (char currentCharacter : text.toCharArray() ) loop variant. Simply because it clearer conveys what you are working with. In addition it removes the need for some extra temporary variables like x, length and trueL

• Do early returns, if possible – As Janos mentions, in your code you have most of your code within the if (str.contains(" ")) block. This can be reversed, and you can do an early return without almost doing any work.

• Include a little more vertical space – A personal nitpick of mine is to add a little more vertical space in the code. Adding an extra newline in front of for loops, and if blocks can greatly enhance the reading and understanding of code.

Refactored solution

Following all of this advice, gives code like this:

public class URL {
 public static String URLify(String text) {
 
 if (!text.contains(" ")) {
 return text;
 }
 // Use urlifiedText for building the result text
 StringBuilder urlifiedText = new StringBuilder();
 
 // Replace spaces with %20, after trimming leading and trailing spaces
 for (char currentChar : text.trim().toCharArray()) {
 if (currentChar == ' ') {
 urlifiedText.append("%20");
 } else {
 urlifiedText.append(currentChar);
 }
 } 
 
 return urlifiedText.toString();
 }
 
 public static void main(String[] args) {
 System.out.println(URLify(" my example text "));
 }
}

Even with some added comments, it still is slightly shorter than your original code, and hopefully understandable.

Update: Alternate implementation

What if you were not allowed to use any of the str.functions()? No str.toCharArray(), str.trim(), str.contains(), and so on? Here is an implementation using the basic String and StringBuilder functionality. If you wanted to you could also replace the StringBuilder method by concatenating into a new String. (Leaving that part to the reader).

A possible implementation could then look like:

/**
 * @description URLifyII ~ Remove leading and trailing spaces,
 * and replace remaining spaces with %20.
 * NB! Without using str.trim(), str.contains(), and so on...
 */
public static String URLifyII(String text) {
 
 int startIndex = 0;
 int endIndex = text.length() - 1;
 StringBuilder urlifiedText = new StringBuilder();
 
 // Find first non-space character
 while (text.charAt(startIndex) == ' ' && startIndex < endIndex) {
 startIndex++;
 }
 
 // Find last non-space character
 while (text.charAt(endIndex) == ' ' && endIndex >= startIndex) {
 endIndex--;
 }
 
 // Repeat text, and replace spaces with %20
 for (int i=startIndex; i <= endIndex; i++) {
 if (text.charAt(i) != ' ') {
 urlifiedText.append(text.charAt(i));
 } else {
 urlifiedText.append("%20");
 }
 }
 
 return urlifiedText.toString();
}

This solution still only loops through the original text just once, but divided into three different parts.

• JollyJoker: I'd use Character.isWhitespace instead of == ' '
• holroy: @JollyJoker, Albeit a good point in the general case, in this particular case I think the requirements said the space character. Not space, tab and/or newline characters.
• JollyJoker: Hard to tell. If the problem statement is a word-by-word copy I'd say it's likely the OP didn't realize whitespace could mean something else.

Answer 2

From a short review:

• If you are going to write your own replace, then you should create a method for it, so that you can call myReplace( string, target, replacement);
• Personally I would have checked if args got a String, and only if nothing is provided would I use the hard coded string, that would make it easier to show and test your design

• No reason to do this in 2 lines:

  str = URLify(str);
  System.out.print(str);
  

  you can just write

  System.out.print(URLify(str));
  

• Javadoc commenting looks good (but is not actually true?), otherwise there are zero comments
• I am pretty you can merge those 2 loops into one if you used a stringbuilder. On the whole the replace algorithm could use work

• Tommy Yamakaitis: Yeah, I auto-created the Javadoc in Eclipse on an earlier draft, and I forgot to edit that part when posting this. It should just say @param str? Correct? Also, what do you mean by the second bullet point? How could I test that? Sorry if that's a dumb question.
• konijn: If you run your program on the command line, then you can pass a string as a parameter to the program. That parameter will be passed to you in the args parameter of the main() method.

Answer 3

The next simplest solution not counting str.replace(...) would have been to use a StringBuilder: for each space append %20, otherwise append the character itself. But I guess you didn't want to do that.

You took extra care to avoid unnecessary processing (by checking if the string contains space), and unnecessary allocations (counting the exact storage size needed). But then the trimming kinda defeats the purpose of the rest of the code: in case anything is trimmed, that will involve the allocation of a new string, and a full iteration over the source. To be consistent with the rest of the code, you could have done the trimming yourself.

Some minor technical improvements are possible:

• Since you only use length and trueL when you know the string contains a space, it would be better to declare those variables in the scope of the if block

• Instead of the long piece of code inside the if (str.contains(" ")) {, you could negate the condition for an early return, and make the code flatter, which is a bit easier to read

• Instead of a counting loop, a for-each loop is more idiomatic when possible. You could create oldArr before the counting loop, and use it in the loop that counts spaces

• Instead of computing the strangely named trueL, you could count the number of spaces, and store it in the naturally named spaces

• Since newArr has the exact size for the result string, you can use the single-parameter constructor of String

• You could declare x in the initializer of the second for loop, to limit its scope to the loop's body

Something like this:

public static String urlencode(String str) {
 str = str.trim();
 if (!str.contains(" ")) {
 return str;
 }
 char[] chars = str.toCharArray();
 int spaces = 0;
 for (char c : chars) {
 if (c == ' ') {
 spaces++;
 }
 }
 char[] newArr = new char[chars.length + 2 * spaces];
 for (int i = 0, x = 0; i < chars.length; i++) {
 char c = chars[i];
 if (c == ' ') {
 newArr[x] = '%';
 newArr[x + 1] = '2';
 newArr[x + 2] = '0';
 x += 3;
 } else {
 newArr[x] = c;
 x++;
 }
 }
 return new String(newArr);
}

Answer 4

Most of the Javadoc is redundant and can be removed. What remains is "Makes a string with spaces URL-friendly".

The variable names should follow a pattern. That is, all variables for the input string should have in in the name, and all output variables should have out. Or at least i and o.

You should have told us why you don't want to use existing libraries because when using libraries, the problem becomes trivial: return in.trim().replace(" ", "%20").

By the way, it's good that your code doesn't need any comments. This means it is still simple enough to understand it by reading alone.