One . subject

1. subject

Please implement a function , Replace each space in a string with “%20”. for example , When the string is We Are Happy. The replaced string is We%20Are%20Happy

2. Basic framework

• C++ Code framework of version

class Solution {
    
public:
	void replaceSpace(char *str,int length) {
    
	
	}
};

3. Original link

Cattle from Replace blank space

Two . Their thinking

1. Thought analysis

$(1)$ Only with the help of $str$ The string pointed to , Move from back to front ;
$(2)$ Replace a space with '%''2''0', Replace one character with three characters , It's equivalent to an increase in 2 Characters ;
$(3)$ A loop counts the number of spaces in the string , The length of the replaced string is the length of the original string plus the number of cells 2 times .
$(4)$ Two variables $end1、end2$ Record the subscript of the last character of the original string and the subscript of the last character of the new string respectively ;
$(5)$ A cycle , If the subscript $end1$ The character of is not a space , Just put $end1$ The subscript character moves to $end2$ Subscript location , Then both subscripts are subtracted 1;
$(6)$ If the subscript $end1$ The characters are spaces ,$end1$ reduce 1,, hold '0'、'2'、'%' These three characters are stored in subscript $end2$ Location , After each deposit $end--$;
$(7)$ When the space replacement is complete ,end1 And end2 equal , End of cycle .

2. Code details

Ideas 1

class Solution {
    
public:
	void replaceSpace(char *str,int length) {
    
        // Number of spaces found 
        int cnt = 0;
        char* start = str;
        while(*start){
    
            if(*start == ' '){
    
                cnt++;
            }
            start++;
        }
        // Move from back to front , Space encountered 
        // Before and after subscript 
        int end1 = length - 1;
        int end2 = length - 1 + 2*cnt;
        while(end1 != end2){
    
            if(str[end1] != ' '){
    
                str[end2--] = str[end1--];
            }
            else{
    
                str[end2--] = '0';
                str[end2--] = '2';
                str[end2--] = '%';
                end1--;
            }
        }
	}
};

Ideas 2

class Solution {
    
public:
	void replaceSpace(char *str,int length) {
    
        // Find the number of spaces 
    char* start = str;
    int cnt = 0;
    while (*start) {
    
        if (*start == ' ') {
    
            cnt++;
        }
        start++;
    }
    int len1 = length;
    int len2 = length + 2 * cnt;
    // Create an array to store new strings 
    char* s = (char*)malloc(sizeof(char) * (len2+1));
    start = str;
    char* ps = s;
    while (*start) {
    
        if (*start != ' ') {
    
            *ps++ = *start++;
        }
        else {
    
            start++;
            *ps++ = '%';
            *ps++ = '2';
            *ps++ = '0';
        }
    }
    *ps = '\0';
    strcpy(str, s);
    free(s);
    s = NULL;
	}
};

3、 ... and . Knowledge and harvest of this topic

$Ontology\; has\; two\; ideas\; ：$
$The\; first\; method\; is\; to\; put\; it\; from\; back\; to\; front\; ,\; There\; is\; no\; need\; to\; create\; a\; new\; array\; .$
The second is the conventional method , From front to back . Create a new character array , Put the contents of the original string into the created character array in turn , If you encounter a space character, put three characters ‘%’、‘2’、‘0’ To character array , Until the end of the string . Then copy the contents of the character array back to the original string .

$END$