Write a method to replace all spaces in a string w

Question

I have a question about a programming problem from the book Cracking The Code Interview by Gayl Laakmann McDowell, 5th Edition.

The problem states: Write a method to replace all spaces in a string with '%20'. Assume string has sufficient space at end of string to hold additional characters, and that you're given a true length of a string. I used the books code, implementing the solution in Java using a character array (given the fact that Java Strings are immutable):

public class Test {
    public void replaceSpaces(char[] str, int length) {
        int spaceCount = 0, newLength = 0, i = 0;

        for(i = 0; i < length; i++) {
            if (str[i] == ' ') 
                spaceCount++;
        }

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

    public static void main(String[] args) {
        Test tst = new Test();
        char[] ch = {'t', 'h', 'e', ' ', 'd', 'o', 'g', ' ', ' ', ' ', ' ', ' ', ' '};
        int length = 6;
        tst.replaceSpaces(ch, length);  
    }
}

The output I am getting from the replaceSpaces() call is: the%20do which is cutting of the last character of the original array. I have been scratching my head over this, can anyone explain to me why the algorithm is doing this?

Answer 1

Question : Urlify the spaces with %20

Solution 1 :

public class Solution9 {
public static void main(String[] args) {
    String a = "Gini Gina Protijayi";


       System.out.println(   urlencode(a));
}//main

public static String urlencode(String str) {
      str = str.trim();
        System.out.println("trim =>" + str);

        if (!str.contains(" ")) {
            return str;
        }

    char[] ca = str.toCharArray();

    int spaces = 0;
    for (char c : ca) {
        if (c == ' ') {
            spaces++;
        }
    }

    char[] newca = new char[ca.length + 2 * spaces];
      //  a pointer x has been added
    for (int i = 0, x = 0; i < ca.length; i++) {
        char c = ca[i];
        if (c == ' ') {
            newca[x] = '%';
            newca[x + 1] = '2';
            newca[x + 2] = '0';
            x += 3;
        } else {
            newca[x] = c;
            x++;
        }
    }
    return new String(newca);
}

}//urlify

Answer 2

I am also looking at that question in the book. I believe we can just use String.trim() and String.replaceAll(" ", "%20) here

Answer 3

public class ReplaceChar{

 public static void main(String []args){
   String s = "ab c de  ";
   System.out.println(replaceChar(s));

 }

 public static String replaceChar(String s){

    boolean found = false;
    StringBuilder res = new StringBuilder(50);
    String str = rev(s);
    for(int i = 0; i <str.length(); i++){

        if (str.charAt(i) != ' ')  { found = true; }
        if (str.charAt(i) == ' '&& found == true) { res.append("%02"); }            
        else{ res.append(str.charAt(i)); }
    }
        return rev(res.toString()); 
 }

 // Function to reverse a string
 public static String rev(String s){
     StringBuilder result = new StringBuilder(50);
     for(int i = s.length()-1; i>=0; i-- ){
        result.append(s.charAt(i));
    }
    return result.toString();
 }}

A simple approach:

1. Reverse the given string and check where the first character appears.
2. Using string builder to append "02%" for spaces - since the string is reversed.
3. Finally reverse the string once again.

Note: We reverse the string so as to prevent an addition of "%20" to the trailing spaces.

Hope that helps!

Answer 4

You are passing the length as 6, which is causing this. Pass length as 7 including space. Other wise

for(i = length - 1; i >= 0; i--) {

will not consider last char.

Answer 5

With these two changes I got the output: the%20dog

1) Change space count to 2 [since length already includes 1 of the 3 characters you need for %20]

newLength = length + (spaceCount * 2);

2) Loop should start on length

for(i = length; i >= 0; i--) {

Answer 6

public String replace(String str) {
    String[] words = str.split(" ");
    StringBuilder sentence = new StringBuilder(words[0]);

    for (int i = 1; i < words.length; ++i) {
        sentence.append("%20");
        sentence.append(words[i]);
    }

    return sentence.toString();
}