String to Url

URL化

分析

从末尾位置 k 开始往前填充字符
从实际字符串末尾 length - 1 开始向前遍历：
- 若遇到普通字符，则复制到末尾
- 若遇到空格 ' '，则插入 '%20'
最后返回处理后的子串 s.substr(k + 1) 即可

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution
{
public:
    string replaceSpaces(string s, int length)
    {
        int k = s.size() - 1;  // k 指向字符串的最末尾（即原始字符串+预留空间）

        // 从真实长度的尾部开始往前处理
        for (int i = length - 1; i >= 0; --i)
        {
            if (s[i] == ' ')  // 空格替换为 "%20"
            {
                s[k--] = '0';
                s[k--] = '2';
                s[k--] = '%';
            }
            else  // 普通字符直接移动
            {
                s[k--] = s[i];
            }
        }

        // 截取有效部分返回
        return s.substr(k + 1);
    }
};