题目描述

原题链接：剑指 Offer 05. 替换空格

解题思路

一、暴力解法

每出现一个空格，就出三个空位置，然后再填充字符。

class Solution {
public:
    string replaceSpace(string s) {
        int cnt = 0;
        // 先统计有几个位置需要替换
        for(int i = 0; i < s.size(); i++) {
            // 注意这里应为' '：代表字符，而" "：代表字符串
            if(s[i] == ' ')     cnt++;                   
        }
        // 更新s的长度
        s.resize(s.size() + cnt * 2);
        int n = s.size();
        for(int i = 0; i < n; i++) {
            // 找到一个空位置，将后续元素移除两个位置
            if(s[i] == ' ') {  
                // 注意边界，从i + 3到n - 1需要被移动
                for(int j = n - 1; j > i + 2; j--) {
                    // 每次需移动两个位置
                    s[j] = s[j - 2];
                }
                // 填充字符
                s[i] = '%';
                s[i + 1] = '2';
                s[i + 2] = '0';
            }
        }

        return s;
    }
};

时间复杂度 $O(n^2)$
空间复杂度 $O(1)$

二、双指针解法

从后往前依次填充。在原字符串位置末尾和新字符串位置末尾分别设置一个尾指针，当原字符串尾指针所指向的不为空格时，将该字符填充到新字符串尾指针所指向位置。当指向为空格时，在新字符串尾指针的开始处并再往前两个位置填充%20。当遍历到i == j时，说明空位置已被替换完，剩下的为非空位置或全遍历完。

class Solution {
public:
    string replaceSpace(string s) {
        int n1 = s.size();
        int cnt = 0;
        for(int i = 0; i < n1; i++) {
            if(s[i] == ' ')     cnt++;
        }
        s.resize(n1 + cnt * 2);
        int n2 = s.size();
        for(int i = n1 - 1, j = n2 - 1; i < j; i--, j--) {  // 当i == j时，说明空位置已被替换完，剩下的为非空位置或全遍历完
            if(s[i] == ' ') {
                s[j--] = '0';
                s[j--] = '2';
                s[j] = '%';     // 每次结束后会有自动地j--，此处不需要再j--
            } else {
                s[j] = s[i];
            }            
        }
        return s;
    }
};

时间复杂度 $O(n)$
空间复杂度 $O(1)$

参考文章：题目：剑指Offer 05.替换空格