剑指offer（C++）——替换空格

不念不忘少年蓝@ 2022-06-17 08:41 99阅读 0赞

## 题目描述 ##

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

**思路：**简单暴力解法，从头到尾遍历字符串，碰到空格，首先将后面的所有字符串往后移动2个字符，才能空出3个字符位子插入字符“%20”，对于一个长度为n的字符串，对每个空格，需要移动后面O(n)个字符，因此包含n个空格的字符串，总的时间复杂度为O(n\*n)。

换个角度，我们从后往前开始替换，首先遍历一遍字符串，统计出空格的个数，并由此能够计算出替换之后的字符串的长度。接着再次从后往前遍历字符串，同时设置两个指针P1和P2，P1指向原始字符串末尾，P2指向替换之后的字符串末尾。我们向前移动P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。然后把P1向前移动一格，在P2之前插入字符串“%20”，同时P2向前移动3格。重复此过程，直到所有的空格都已替换完。这种做法的时间复杂度为O(n)。

代码实现：

class Solution {
    public:
    	void replaceSpace(char *str, int length) {
    		if (str == NULL || length < 0)
    			return;
    		else
    		{
    			int numoforiginal = 0;            //用来统计字符串长度
    			int numofspace = 0;                //用来统计空格数
    			int i = 0;
    			while (str[i] != '\0')
    			{
    				numoforiginal++;               //统计字符串长度
    				if (str[i++] == ' ')
    					numofspace++;              //空格数
    			}
    			int newoflength = numoforiginal + numofspace * 2;
    			if (newoflength > length)
    				return;
    
    			//从后往前替换空格
    			int indexoforiginal =numoforiginal;                          
    			int indexofnew = newoflength;
    			while (indexoforiginal >= 0 && indexofnew > indexoforiginal)
    			{
    				if (str[indexoforiginal] == ' ')
    				{
    					str[indexofnew--] = '0';
    					str[indexofnew--] = '2';
    					str[indexofnew--] = '%';
    				}
    				else
    					str[indexofnew--] = str[indexoforiginal];
    				indexoforiginal--;
    			}
    		}
    	}
    };