Leetcode - Sword finger offer 05 Replace spaces

summary

The finger of the sword Offer 05. Replace blank space

analysis

• This question , If the space complexity is not limited , It's very simple , Just open a new one string It can be realized

• however , If the request can only be handled in principle ？ There is a problem to be solved ：

  • s --> %20, Added characters , Need to increase the striing The capacity of

    because push_back It can be the last operation

Ideas

Add capacity

• You can traverse it first string, Count the number of spaces , You can know the final size that needs to be expanded
• And then use it resize() To expand the size

Code

class Solution {
    
public:
    string replaceSpace(string s) {
    
        int count = 0; //  Count the number of spaces 
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
    
            if (s[i] == ' ') {
    
                count++;
            }
        }
        //  Extended string s Size , That is, replace each space with "%20" After the size of 
        s.resize(s.size() + count * 2);
        
        //  In order to operate in situ , So use double finger acupuncture 
        int ptr = s.size() - 1, wokr_ptr = sOldSize - 1;
        //  This is from the back to the front , Because if you add new elements from front to back , Will overwrite the original elements （ 
        for(; wokr_ptr >= 0; --wokr_ptr) {
    
            if (s[wokr_ptr] != ' ')   s[ptr--] = s[wokr_ptr];
            else {
    
                s[ptr] = '0';
                s[ptr - 1] = '2';
                s[ptr - 2] = '%';
                ptr -= 3;
            }
        }
        return s;
    }
};