~4.1 sword finger offer 05. replace spaces

Title Description

Ideas

C++:
stay C++ In language , string Designed to 「 variable 」 The type of , Therefore, you can modify in place without creating a new string .

Ideas ：
（1）1 Spaces become %20, The length will increase 2.
— So first count the number of spaces , Then change string The length of
（2）i Point to the end of the original string ,j Point to the end of the current string , ij Represents that there is no space left of the original string
— If s[i]!=’ ’ that s[j]=s[i]
— If s[i]’ ’ Then close the string [j-2, j] The element of is changed to “%20”,j=j-2

I know for the first time string It's actually of variable length , Originally, my problem is that I don't know the length of the input string , Therefore, the length of the array cannot be determined , Take it at last vector Realized ,vector Implementation is similar to java,python, You don't need to know the length in advance . The idea is very simple , If it's a space, add it ’%20’, Instead of adding the original string .

Source code

C++

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


class Solution {
    
public:
    string replaceSpace(string s) {
    
        //vector The function is void That's it 
        vector<char > v;
        for (char c : s) {
    
            if (c==' '){
    
                v.push_back('%');
                v.push_back('2');
                v.push_back('0');
            } else{
    

                v.push_back(c);
            }

        }
        for (int i = 0; i <v.size() ; i++) {
    
            cout<<v[i];

        }
        cout<<endl;
        
        
        // change string Length solution ：
        int count = 0, len = s.size();
        //  Count the number of spaces 
        for (char c : s) {
    
            if (c == ' ') count++;
        }
        //  modify  s  length 
        s.resize(len + 2 * count);
        //  Traversal modification in reverse order 
        for(int i = len - 1, j = s.size() - 1; i < j; i--, j--) {
    
            if (s[i] != ' ')
                s[j] = s[i];
            else {
    
                s[j - 2] = '%';
                s[j - 1] = '2';
                s[j] = '0';
                j -= 2;
            }
        }
        return s;

    }
};

int main (){
    
    Solution solution;
    string s="We are friend!";
    string re=solution.replaceSpace(s);
    cout<<re<<endl;
    return 0;
}

java:

class Solution {
    
    public String replaceSpace(String s) {
    
        StringBuilder res = new StringBuilder();
        for(Character c : s.toCharArray())
        {
    
            if(c == ' ') res.append("%20");
            else res.append(c);
        }
        return res.toString();
    }
}