Replace spaces

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Question: please to implement a function spaces, each string is replaced by the “%20”. For example, the input “ We are happy.&rdquo, then the output;“We%20are%20happy.”.
    See this topic, we should first think of is originally a space character, after the replacement of a '%','2'and'0' these 3 characters, so the string variable length. If it is to do the replacement in the original string, then it is possible to cover the changes in the string back memory. If you are creating a new string and replacement in the new string, then we can allocate enough memory.
     Here introduces a time complexity of O (n) solution.
     We can first traversal of a string, so it can count the total string space, the total length of string and can be calculated from the following replacement. Each replacement of a space, increase the length of 2, so after the replacement string is equal to the length of the original length and number 2 times spaces. We use the string "We are happy." for example, "14 We are happy." this string length (including the end symbol'我们可以先遍历一次字符串, 这样就能统计出字符串中空格的总数, 并可以由此计算出替换之后的字符串的总长度. 每替换一个空格, 长度增加2, 因此替换以后字符串的长度等于原来的长度加上2乘以空格数目. 我们以字符串"We are happy."为例, "We are happy."这个字符串的长度是14(包括结尾符号'\0'), 里面有两个空格, 因此替换之后字符串的长度是18'), there are two spaces, so after the replacement of the length of the string is 18.
     We start to copy and replace strings from behind. First prepare the two pointer, P1 and P2. At the end of the P1 to the original string, and P2 refers to the end of string replacement after the (as shown in figure (a)). Then we move the pointer P1, one by one to which it points characters are copied to the P2 point position, until he came to the first blank. The string contains such as shown in figure (b), a gray background region is made character copy (mobile) region. With the first space, the P1 moves forward 1 spaces, insert the string before P2"%20". Because of the "%20" of length 3, but also to the P2 moves forward 3 spaces such as shown in figure (c).
    We then forward copy, until he came to second spaces (such as shown in figure (d)). Once again, we put the P1 moves forward 1 spaces, and the P2 moves forward 3 spaces into the "%20" (as shown in figure (E)). At this timeP1 and P2 point to the same location, showed that all the spaces have been replaced..

Note: the figure with a shadow areas are the moving character. (a) the end of a first pointer to the string, the end of the second pointer to the string replacement after the. (b) followed by copying the contents of a string, until the first pointer encountered the first space. (c) the first space is replaced with the'%20', the first pointer moves forward 1 spaces, the second pointer moves forward 3 spaces. (d) followed by forward copy the characters in a string, until it touches the spaces. (E) the replacement string in the countdown to second spaces, the first pointer moves forward 1 spaces, the second pointer moves forward 3 spaces.
Reference code:
 1 /*Length is the total capacity of a character array string*/
 2 void ReplaceBlank(char string[], int length)
 3 {
 4     if(string == NULL && length <= 0)
 5         return;
 6  
 7     /*OriginalLength is the actual length of the string string*/
 8     int originalLength = 0;
 9     int numberOfBlank = 0;
10     int i = 0;
11     while(string[i] != '\0')
12     {
13         ++ originalLength;
14  
15         if(string[i] == ' ')
16             ++ numberOfBlank;
17  
18         ++ i;
19     }
20  
21     /*NewLength is the space is replaced with the'%20'length*/
22     int newLength = originalLength + numberOfBlank * 2;
23     if(newLength > length)
24         return;
25  
26     int indexOfOriginal = originalLength;
27     int indexOfNew = newLength;
28     while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
29     {
30         if(string[indexOfOriginal] == ' ')
31         {
32             string[indexOfNew --] = '0';
33             string[indexOfNew --] = '2';
34             string[indexOfNew --] = '%';
35         }
36         else
37         {
38             string[indexOfNew --] = string[indexOfOriginal];
39         }
40  
41         -- indexOfOriginal;
42     }
43 }


The complete code:
 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4  
 5 /*Length is the total capacity of a character array string*/
 6 void ReplaceBlank(char string[], int length)
 7 {
 8     if(string == NULL && length <= 0)
 9         return;
10  
11     /*OriginalLength is the actual length of the string string*/
12     int originalLength = 0;
13     int numberOfBlank = 0;
14     int i = 0;
15     while(string[i] != '\0')
16     {
17         ++ originalLength;
18  
19         if(string[i] == ' ')
20             ++ numberOfBlank;
21  
22         ++ i;
23     }
24  
25     /*NewLength is the space is replaced with the'%20'length*/
26     int newLength = originalLength + numberOfBlank * 2;
27     if(newLength > length)
28         return;
29  
30     int indexOfOriginal = originalLength;
31     int indexOfNew = newLength;
32     while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
33     {
34         if(string[indexOfOriginal] == ' ')
35         {
36             string[indexOfNew --] = '0';
37             string[indexOfNew --] = '2';
38             string[indexOfNew --] = '%';
39         }
40         else
41         {
42             string[indexOfNew --] = string[indexOfOriginal];
43         }
44  
45         -- indexOfOriginal;
46     }
47 }
48  
49 int main()
50 {
51     const int length = 100;
52  
53     char string[length] = "hello world.";
54  
55     ReplaceBlank(string, length);
56  
57     int newLength = strlen(string);
58 /*
59     int newLength = 0;
60     int j = 0;
61     while(string[j] != '\0')
62     {
63         newLength++;
64         ++j;
65     }
66 */
67     for(int i = 0 ; i <newLength ; ++i)
68         cout<<string[i];
69     cout<<endl;
70  
71     return 0;
72 }



Test code:
#include <stdio.h>
#include <string>

/*Length is the total capacity of a character array string*/
void ReplaceBlank(char string[], int length)
{
    if(string == NULL && length <= 0)
        return;

    /*OriginalLength is the actual length of the string string*/
    int originalLength = 0;
    int numberOfBlank = 0;
    int i = 0;
    while(string[i] != '\0')
    {
        ++ originalLength;

        if(string[i] == ' ')
            ++ numberOfBlank;

        ++ i;
    }

    /*NewLength is the space is replaced with the'%20'length*/
    int newLength = originalLength + numberOfBlank * 2;
    if(newLength > length)
        return;

    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(string[indexOfOriginal] == ' ')
        {
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '2';
            string[indexOfNew --] = '%';
        }
        else
        {
            string[indexOfNew --] = string[indexOfOriginal];
        }

        -- indexOfOriginal;
    }
}

void Test(char* testName, char string[], int length, char expected[])
{
    if(testName != NULL)
        printf("%s begins: ", testName);

    ReplaceBlank(string, length);

    if(expected == NULL && string == NULL)
        printf("passed.\n");
    else if(expected == NULL && string != NULL)
        printf("failed.\n");
    else if(strcmp(string, expected) == 0)
        printf("passed.\n");
    else
        printf("failed.\n");
}

// The space in the middle of a sentence
void Test1()
{
    const int length = 100;

    char string[length] = "hello world";
    Test("Test1", string, length, "hello%20world");
}

// The space at the beginning of a sentence
void Test2()
{
    const int length = 100;

    char string[length] = " helloworld";
    Test("Test2", string, length, "%20helloworld");
}

// The space at the end of the sentence
void Test3()
{
    const int length = 100;

    char string[length] = "helloworld ";
    Test("Test3", string, length, "helloworld%20");
}

// Continuous two spaces
void Test4()
{
    const int length = 100;

    char string[length] = "hello  world";
    Test("Test4", string, length, "hello%20%20world");
}

// Introduction of NULL
void Test5()
{
    Test("Test5", NULL, 0, NULL);
}

// The incoming content as an empty string
void Test6()
{
    const int length = 100;

    char string[length] = "";
    Test("Test6", string, length, "");
}

//The incoming string content for a space
void Test7()
{
    const int length = 100;

    char string[length] = " ";
    Test("Test7", string, length, "%20");
}

// The incoming string with no spaces
void Test8()
{
    const int length = 100;

    char string[length] = "helloworld";
    Test("Test8", string, length, "helloworld");
}

// String passed in all spaces
void Test9()
{
    const int length = 100;

    char string[length] = "   ";
    Test("Test9", string, length, "%20%20%20");
}

int main(int argc, char* argv[])
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();
    Test8();
    Test9();

    return 0;
}



 
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Rory at November 16, 2013 - 2:58 AM