算法-字符串替换空格

ゝ一世哀愁。 2022-06-10 03:50 334阅读 0赞

**题目：**  
实现一个函数，把字符串中的每一个空格替换成”%20”。例如输入”We are happy.”，则输出”We%20are%20happy.”。

**解题思路：**  
首先我们需要先想清楚一点，函数就要求输出替换后的结果，没有说是在原数据上替换，还是可以申请内存，创建一个新的字符串？  
后者可以让问题变得简单，用比较直接的方式就可以实现一个时间复杂度为O(n)的代码，首先我们先遍历一遍字符串，找到到底有多少个空格以计算出替换后的长度，在上面的例子中，替换前是14，替换后是18，创建一个长度为18的数组，然后我们只要在从头遍历一次原字符串，没有出现空格就直接复制原字符串的内容，出现空格了就写入”%20”：

![这里写图片描述][SouthEast]

虽然这种方法得到了一个时间复杂度为O(n)的算法，但是一样牺牲了空间复杂度啊，要是我们只考虑在原数据上替换，而不新建数组呢？

那么这里有个前提条件，我们只能认为题目中给我们的数组长度是大于等于18的，要不然就会放不下，所以我们还可以先计算一下替换后的长度，然后加个判断，如果发现原数组长度不够，那就直接return好了，这样就可以成功甩锅！

假设原始数据是这样的（最起码也要是这样）：  
![这里写图片描述][SouthEast 1]  
如果我们还是从前到后的遍历的话，时间复杂度就会变成O(n^2)，因为每次遍历到空格的时候，还会带动着其他的数据向后移动：  
![这里写图片描述][SouthEast 2]

所以，有没有什么办法能够兼顾时间复杂度和空间复杂度呢？？  
**用直接修改原数据的方法，从后向前替换空格！**就酱：  
![这里写图片描述][SouthEast 3]  
这种方法的话，计算替换后的长度就有了一个新的作用，它告诉我们原数据中最后一位放在新数据的哪一位。

**代码实现：**

//length就是数组创建时候的长度
    void ReplaceBlank(char string[], int length)
    {
        if(string == NULL && length <= 0)
            return;
    
        //实际有数据的长度
        int originalLength = 0;
        int numberOfBlank = 0;
        int i = 0;
        while(string[i] != '\0')
        {
            ++ originalLength;
    
            if(string[i] == ' ')
                ++ numberOfBlank;
    
            ++ i;
        }
    
        //替换之后，新的数据需要的长度 
        int newLength = originalLength + numberOfBlank * 2;
        //在这里甩锅啦，让我在原数据上改，还不给够长度，我能怎么办？
        if(newLength > length)
            return;
    
        int indexOfOriginal = originalLength;
        int indexOfNew = newLength;
        while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
        {
            if(string[indexOfOriginal] == ' ')
            {
                string[indexOfNew --] = '0';
                string[indexOfNew --] = '2';
                string[indexOfNew --] = '%';
            }
            else
            {
                string[indexOfNew --] = string[indexOfOriginal];
            }
    
            -- indexOfOriginal;
        }
    }

[SouthEast]: /images/20220610/d531515ef42d43a3911017a6472cfcf4.png
[SouthEast 1]: /images/20220610/5496fa3784c747d9ac765732ccb3c4ef.png
[SouthEast 2]: /images/20220610/83917d3441b04c32b0fc2dcf8aaf9dff.png
[SouthEast 3]: /images/20220610/1b703a1ba278403d8cc3e91051bb84e9.png