05.替换空格

题目链接

题目描述

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

示例

示例1：

输入：s = “We are happy.” 输出：“We%20are%20happy.”

提示

• 0 <= s 的长度 <= 10000

  思路

  双指针

  首先将字符串扩充到替换后的大小。
  设置两个指针 left 和 right ，分别指向原字符串末尾和新字符串末尾。

• 若 left 所指的字符不为空格，则将其后移到 right 处

• 若 left 所指的字符是空格，则从 right 开始的向前依次填充 '0', '2', '%'

  题解

  class Solution {
  public:
    string replaceSpace(string s) {
        int count = 0;
        int oldSize = s.size();
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == ' ') {
                ++count;
            }
        }
        s.resize(s.size() + count * 2);
        int newSize = s.size();
        for (int right = newSize - 1, left = oldSize - 1; left < right; --right, --left) {
            if (s[left] != ' ') {
                s[right] = s[left];
            } else {
                s[right] = '0';
                s[right - 1] = '2';
                s[right - 2] = '%';
                right -= 2;
            }
        }
        return s;
    }
  };

  复杂度分析

• 时间复杂度：

• 空间复杂度：