Replacing all spaces in a string with '%20' (C++)

Question

Having some trouble understanding parts of the code; the output I am getting is also wrong. The problem is to replace all spaces in a string with '%20'. The full code is shown below; it compiles but doesn't run exactly as it should.

#include <iostream>
#include <string>
using namespace std;

void replaceSpaces(string str){

    //Getting the length of the string, counting the number of spaces 
    int strLen = str.length();
    int i, count = 0;
    for (i = 0; i <= strLen; i++) {
        if(str[i]==' ')
        count++;
    }

    //Determining the new length needed to allocate for replacement characters '%20'
    int newLength = strLen + count * 2;

    str[newLength] = '\0';
    for (i = strLen - 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;
        }
    }
    cout << str <<endl;

}

int main() {

    string str = "hello jellybean hello";
    replaceSpaces(str);

    return 0;

}

---

I am probably missing something obvious, but when allocating for the new string length in this line:

int newLength = strLen + count * 2;

Here we are multiplying the number of spaces by 2, but if we are trying to replace all spaces with '%20', why not multiply it by 3?

---

str[newLength] = '\0';

Does this line indicate that the position past the last character in the string is assigned a null space?

---

Am also confused about the else statement.

 else {
        str[newLength - 1] = str[i];
        newLength = newLength -1;
    }

Not sure if I completely understand the circumstance when this would be executed.

---

When the functions are compiled and run, if

string str = "hello jellybean hello";

the expected output would be hello%20jellybean%20hello, except the output I am getting is hello%20jellybean%20h.

In terms of time complexity, since there are two independent for loops, would the time complexity be O(n)?

I know I'm asking a lot of different questions, many thanks in advance for any answers!

Answer 1

This is wrong:

str[newLength] = '\0';

std::string objects maintain their NUL terminator internally based on their size. You want

str.resize(newLength);

instead.

Answer 2

int newLength = strLen + count * 2;

says to allocate space (later), equal to the length of the string, plus the number of whitespaces found multiplied by two, which makes sense.

For example: so glad to help, should use the slots that the whitespaces live into for the % and they will need two more slots each, for the 20 part of the replacement that will come into play.

---

This is WRONG:

str[newLength] = '\0';

can't you see? You access memory out of the bounds of your string. You act like you actually allocated space equal to the newLength, but you haven't that anywhere in the code yet.

Out of bounds accessing result in Undefined Behavior and that's bad.

---

The else statement is just for copying non-whitespace characters, but you should already given up on that code (if it's not yours) and start from scratch or/and take a sneak peak at: Encode/Decode URLs in C++.

---

As for the wrong result, you should know by reaching that point of that answer, that this is expected.

Answer 3

Trying to do the modification in place is tricky. It's much easier to create a new string:

std::string new_string;
for (int i = 0; i < str.length(); ++i) {
    if (str[i] == ' ')
        new_string += "%20";
    else
        new_string += str[i];
}
return new_string;

or, if you like range-for:

std::string new_string;
for (char ch : str) {
    if (ch == ' ')
        new_string += "%20";
    else
        new_string += ch;
}
return new_string;

Answer 4

You can change that string argument in function to reference, then there wont be any need for new string, at other part of the code, you can use insert function to add '2' and '0', and you only need to convert space to '&'.

void replaceSpaces(string &str) {
        size_t strLen = str.length();
        for (int i = 0; i < strLen; i++) {
            if (str[i] == ' ') {
                str[i] = '%';
                str.insert(str.begin() + i + 1, '2');
                str.insert(str.begin() + i + 2, '0');
                strLen += 2;
            }
        }
    }

Answer 5

This is easy; replace examplestring with your string in the code, and use as you would:

#include <iostream> //debug output
#include <string>

using std::string;
using std::cout;
using std::endl;

//the string to convert
string examplestring = "this is the example string for spaces into %20";

int main()
{
    int countspaces = 0; //its faster to fill a known size
    for (auto &x : examplestring)if (x == ' ')countspaces++; //counts spaces

    string newstring; //declare new string
    newstring.resize(examplestring.size() + (countspaces*3)); //pre-set size to make it run faster

    int newstringiterator = 0; //keep track of new string location

    //if ' '(space), place %20 in newstring and add 3 to iteration
    //else just place the letter and iterate

    for (int i=0;i<examplestring.size();i++)
    {
        if (examplestring[i] == ' ') 
        { 
            newstring.insert(newstringiterator, "%20");
            newstringiterator += 3;
        }
        else newstring[newstringiterator++] = examplestring[i];
    }

  //final newstring is the original with %20 instead of spaces. 
  cout << newstring << endl;

  system("PAUSE"); //to read console output
  return 0; //return to zero
}

This will output newstring, which is the old string with '%20' instead of spaces.