剑指 Offer 05. 替换空格

题目描述

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

解题思路

方法一：使用额外空间

        使用额外的空间存储替换后的字符串，逐个字符遍历原始字符串，如果遇到空格就用"%20"，其他字符就直接复制到新的字符串中，结果返回新字符串。

        需要遍历整个字符串，因此时间复杂度是O(n)；需要额外空间存储新的字符串，因此空间复杂度是O(n)。

方法二：原地替换（从后向前遍历）

        这种方法可以在不使用额外空间的情况下完成替换。首先计算出替换后的字符串长度，然后从原字符串的末尾开始遍历，遇到非空格字符则复制到新的位置，遇到空格则替换为"%20"。由于是从后往前遍历，不会覆盖未处理的字符。

        之所以从后往前复制是为了避免覆盖未复制的字符，如果从前往后复制，当将一个字符移动到新的位置时，原始字符会被覆盖，导致信息丢失或紊乱。通过resize函数将原始字符串扩充空间会在字符串末尾开辟出新的空间，由于是新开辟的，没有任何数据，不会影响到其他字符。

        遍历整个字符串两次，时间复杂度是O(n)；原地替换不需要使用额外的空间，空间复杂度是O(1)。

代码及结果

使用额外空间

std::string Solution::replaceSpace(std::string s)
{
    std::string result = "";
    std::string temp = "%20";
    for (char c : s)
    {
        if (c == ' ')
            result += temp;
        else
            result += c;
    }
    return result;
}

 

原地替换（从后向前遍历）

std::string Solution::replaceSpace(std::string s)
{
    int spaceCount = 0;
    for (char c : s)
    {
        if (c == ' ')
            spaceCount++;
    }
 
    int oldLength = s.length();
    int newLength = oldLength + spaceCount * 2;
 
    s.resize(newLength);
 
    for (int i = oldLength - 1, j = newLength - 1; i >= 0; i--)
    {
        if (s[i] == ' ')
        {
            s[j--] = '0';
            s[j--] = '2';
            s[j--] = '%';
        }
        else
            s[j--] = s[i];
    }
    return s;
}