02 替换空格

题目描述

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

示例：

输入: "We Are Happy"
输出: "We%20Are%20Happy"

解题思路

核心思想：先计算空格数量，确定新字符串长度，然后从后向前替换，避免移动字符。

关键步骤：

1. 统计原字符串中空格的数量
2. 计算新字符串的长度 = 原长度 + 空格数 × 2（每个空格替换为%20，增加2个字符）
3. 使用双指针，从后向前遍历
4. 原指针指向原字符串末尾，新指针指向新字符串末尾
5. 遇到空格则替换为"%20"，否则复制原字符

时间复杂度：O(n) 空间复杂度：O(n)

Python 实现

def replace_space(s):
    """
    替换字符串中的空格为%20

    Args:
        s: 原字符串

    Returns:
        str: 替换后的字符串
    """
    if not s:
        return s

    # 统计空格数量
    space_count = s.count(' ')
    # 计算新字符串长度
    new_length = len(s) + space_count * 2

    # 转换为列表便于修改
    result = [''] * new_length
    p1, p2 = len(s) - 1, new_length - 1

    # 从后向前遍历
    while p1 >= 0:
        if s[p1] == ' ':
            result[p2-2:p2+1] = ['%', '2', '0']
            p2 -= 3
        else:
            result[p2] = s[p1]
            p2 -= 1
        p1 -= 1

    return ''.join(result)


# Python简洁写法
def replace_space_simple(s):
    """
    Python简洁写法
    """
    return s.replace(' ', '%20')


# 测试代码
if __name__ == "__main__":
    test_str = "We Are Happy"
    print(replace_space(test_str))           # We%20Are%20Happy
    print(replace_space_simple(test_str))    # We%20Are%20Happy
    print(replace_space(" "))                # %20
    print(replace_space(""))                 # ""

图解

原字符串: "We Are Happy"
索引:      0 1 2 3 4 5 6 7 8 9 10 11

空格数 = 2
新长度 = 12 + 2*2 = 16

从后向前替换:
step 1: p1=11, s[11]='y' → result[13]='y'
step 2: p1=10, s[10]='p' → result[12]='p'
step 3: p1=9,  s[9]='P' → result[11]='P'
step 4: p1=8,  s[8]=' ' → result[8:11]='%20'
step 5: p1=7,  s[7]='e' → result[7]='e'
...

结果: "We%20Are%20Happy"