面试题05.替换空格

2020-05-27

题目

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：
1
2
输入：s = "We are happy."
输出："We%20are%20happy."
限制：

0 <= s 的长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

暴力法

最暴力的方法就是直接把空格替换为%，然后插入20，然而注意string和vector一样是不支持随机插入和删除的，因为这两个容器将元素保存在连续的内存空间中，在中间插入元素会导致后面的元素全部都要移动。因此，每替换一个空格都需要 $O(N)$ 的时间复杂度，总的时间复杂度为 $O(N^2)$ 。

优化

由于上述算法最大的开销是移动元素，我们观察到这中间实际上存在重复计算，而每个元素最少需要移动一次，因此我们在移动元素时需要确定其最终位置。

每替换一个空格，字符串长度+2，即空格之后所有元素都要向右偏移两格。

而从左向右遍历并插入和移动元素会导致后面的元素被覆盖，因此我们从右向左遍历避免这个问题。

class Solution {
public:
    string replaceSpace(string s) {
        int space_num = 0;
        for(const auto& c:s) {
            if(c == ' ') ++space_num;
        }
        s.append(2*space_num, 0);
        for(auto p1=s.rbegin()+2*space_num, p2=s.rbegin(); p1!=s.rend(); ++p1) {
            if(*p1 != ' ') *(p2++) = *p1;
            else {
                *(p2++) = '0';
                *(p2++) = '2';
                *(p2++) = '%';
            }
        }
        return s;
    }
};

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