题目描述

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

注意：C++解法中，给定的字符串结尾后面还有一定的空间，不然我们还得重新给它分配足够的内存空间才能将空格换成%20。在写题过程中，我们需要判断替换后的字符串是否会超过给定的内存空间长度，超过了就直接返回。Java解法需要自己重新分配内存空间。

解题思路

O(n2)的思路就不写了，直接就是从前开始遍历，遇到空格就将后面所有剩余的字符串往后移动两个位置，然后前面的空格后面就多了两个空位置，写上%20即可。

O(n)的解法：
这种题型，要很容易想到从后往前扫描字符串。我们可以这样：先计算出该字符串有几个空格，然后算出替换后的字符串一共需要多少空间的长度。我们从字符串的后面开始准备复制和替换。可以看以下图示过程：

其中，p2是指向替换后字符串的结尾处应该在哪里，p1是指向替换前，字符串的结尾处。

我们从字符串的后面开始复制和替换，当p1指向的是字符，则将字符复制给p2位置。同时，p1和p2同时向前移动。当p1遇到空格，则p2处赋值字符’0’；p2再向前移动一格，p2处赋值字符’2’；p2再向前移动一格，p2处赋值字符’%’。然后p1和p2再同时向前移动一格。以此类推最终将所有空格替换完成。

java代码：

public class Solution {
    public String replaceSpace(StringBuffer str) {
    	int knum=0;
        /*计算空格的数量与字符串的长度*/
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' ')
                knum++;
        }
        /* 替换空格后的字符串的长度 */
        int newlen=str.length()+2*knum;
        int p1=str.length()-1,p2=newlen-1;
        str.setLength(newlen);
        while(p1>=0 && p2>p1){s
            if(str.charAt(p1)==' '){
                str.setCharAt(p2--, '0');
                str.setCharAt(p2--, '2');
                str.setCharAt(p2--, '%');
                --p1;
            }else{
                str.setCharAt(p2--, str.charAt(p1--));
            }
        }
        return str.toString();
    }
}

C++代码：

class Solution {
public:
	void replaceSpace(char *str,int length) {
        int strlen=0,knum=0,i=0;
        /*计算空格的数量与字符串的长度*/
        while(str[i]!='\0'){
            strlen++;
            if(str[i]==' ') ++knum;
            i++;
        }
        /* 替换空格后的字符串的长度 */
        int newlen=strlen+2*knum;
        /* 如果替换后的长度超过了给出的固定长度则返回 */
        if(newlen>length)return;
        int p1=strlen,p2=newlen;
        while(p1>=0 && p2>p1){
            if(str[p1]==' '){
                str[p2--]='0';
                str[p2--]='2';
                str[p2--]='%';
                --p1;
            }
            else{
                str[p2--]=str[p1--];
            }
        }
	}
};

总结

遇到这种字符串替换的问题，如果时间复杂度达到O(n2),则考虑从后往前替换。同时注意要将复制的过程用图示画出来，才不会导致编程出错。

探讨学习加：
qq：1126137994
微信：liu1126137994

【剑指offer - C++/Java】2、替换空格

文章目录

题目描述

解题思路

总结