字符串空格替换函数实现

题目

字符串空格替换函数实现

信息

• 类型：问答
• 难度：⭐⭐

考点

指针操作,内存管理,字符串处理,算法设计

快速回答

实现函数将字符串中的空格替换为"%20"，要求原地修改且保证空间足够。核心步骤：

1. 遍历字符串统计空格数量
2. 计算新字符串总长度（原长度 + 空格数×2）
3. 从后向前遍历并替换：
   • 非空格字符直接复制
   • 遇到空格写入"%20"

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

解析

原理说明

该问题考察对C字符串（以'\0'结尾的字符数组）的原地修改能力。关键点在于：

• 从后向前处理：避免多次移动字符（向前处理会导致每次替换都要移动后续所有字符）
• 双指针技巧：一个指针指向原字符串末尾，另一个指向新字符串末尾
• 内存预计算：根据空格数提前确定新字符串长度

代码示例

void replaceSpaces(char *str) {
    if (str == NULL) return;

    int spaceCount = 0;
    int originalLen = 0;

    // 统计空格数量和原始长度
    for (int i = 0; str[i] != '\0'; i++) {
        originalLen++;
        if (str[i] == ' ') spaceCount++;
    }

    int newLen = originalLen + spaceCount * 2;
    int i = originalLen;    // 原字符串末尾
    int j = newLen;         // 新字符串末尾

    // 从后向前替换
    while (i >= 0 && j > i) {
        if (str[i] == ' ') {
            str[j--] = '0';
            str[j--] = '2';
            str[j--] = '%';
        } else {
            str[j--] = str[i];
        }
        i--;
    }
}

最佳实践

• 边界检查：函数开头验证指针非NULL
• 终止条件：循环终止条件 j > i 确保提前完成时退出
• 常量使用：用 spaceCount * 2 而非魔数（magic number）
• 效率保障：单次遍历完成操作，时间复杂度O(n)

常见错误

• 未预留足够空间：调用方必须确保缓冲区足够容纳新字符串
• 从前向后替换：导致O(n²)时间复杂度（每次替换移动后续所有字符）
• 忘记结束符：C字符串必须以'\0'结尾，代码中 str[newLen] = '\0' 可显式添加（但示例中j从newLen开始，i从原结尾开始，隐含了结束符处理）
• 指针越界：未正确计算新长度可能导致写溢出

扩展知识

• URL编码原理：空格在URL中被编码为%20，其他特殊字符如'/'编码为%2F
• 内存重叠处理：当源地址和目标地址重叠时（如本例），必须确保复制方向不会覆盖未处理数据
• 变种问题：如果要求支持动态扩容，需结合realloc实现，但会改变空间复杂度
• C字符串特性：区别于C++的std::string，C字符串需手动管理内存且不可变长