剑指Offer05.替换空格

题目描述

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

解法一：遍历添加

由于每次替换都要把一个空格字符变成三个字符，所以我们可以选择使用字符数组方便地进行替换

建立字符数组的长度为s字符串长度的3倍，这样可以保证就算字符串全是空格，也可以容纳所有替换后的字符串

过程如下

• 1、获得字符串s的长度length
• 2、创建字符数组arr，长度为length*3
• 3、初始化size为0，size表示替换后的字符串长度
• 4、从左到右遍历字符串s
  • 获得当前s的当前字符c
  • 如果字符c是空格，则令arr[size]='%',arr[size+1]='2',arr[size+2]=0，并将size的值加3
  • 如果字符c不是空格，则令arr[size]=c，并将size的值加1
• 5、遍历结束后，size的值等于替换后的字符串的长度，从arr的前size个字符创建新字符串，并返回

    public String replaceSpace(String s) {
        int length = s.length();
        char[] arr = new char[length*3];
        int size = 0;
        for(int i=0;i<length;i++){
            char c = s.charAt(i);
            if(c==' '){
                arr[size++]='%';
                arr[size++]='2';
                arr[size++]='0';
            }else{
                arr[size++] = c;
            }
        }
        return new String(arr,0,size);
    }

解法二：原地修改

在解法一中，我们需要额外使用一个数组空间，这样导致我们的空间复杂度为O（n）

我们思考一种不需要额外空间的方法，很明显，我们需要使用双指针

在使用双指针之前，我们需要先扩充一下原字符串的长度

算法过程如下：

• 1、初始化：记录空格数量count，字符串s的长度length
• 2、统计空格数量：遍历s，遇到空格则count++
• 3、修改字符串s的长度：添加完%20后的字符串长度应为length+2*count
• 4、倒序遍历修改：i指针指向原字符串的末尾，j指针指向新字符串的末尾，当i==j时跳出循环
  • 当s[i]不为空格时，执行s[i]=s[j]
  • 当s[i]为空格时，将字符串闭区间[j-2,j]的元素修改为“%20”，同时j-=2；
• 5、返回已经修改好的字符串

    public String replaceSpace(String s) {
        //判空进行剪枝操作
        if(s==null||s.length()==0){
            return s;
        }
        //给字符扩充空间
        StringBuilder str = new StringBuilder();
        //每遇到一次空格，就将新字符串扩充两个单位
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==' '){
                str.append("  ");
            }
        }
        //如果没有空格则直接返回
        if(str.length()==0){
            return s;
        }
        //有空格情况，定义两个指针
        //左指针指向原始字符串的最后一个位置
        int left = s.length()-1;
        //字符串拼接
        s+=str.toString();
        //右指针指向新字符串的最后一个位置
        int right = s.length()-1;
        char[] chars = s.toCharArray();
        while(left>=0){
            if(chars[left]==' '){
                chars[right--]='0';
                chars[right--]='2';
                chars[right]='%'; 
            }else{
                chars[right] = chars[left];
            }
            left--;
            right--;
        }
        return new String(chars);
    }