剑指offer替换空格

题目描述

    请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为 We Are Happy. 则经过替换之后的字符串为 We%20Are%20Happy。（本题用 Java 实现，提供的字符串是 StringBuffer 类型）

思路分析

    最直接暴力的解法，新创建一个字符串，遍历原字符串，遇到字符直接存到新字符串中，遇到空格，把“%20”存到新字符串中。这样时间复杂度是 O(n)，空间复杂度也是 O(n)。那么是否可以不开辟新的字符串空间，直接在原字符串上操作呢？
    ”%20″ 比空格的长度要多两位，所以想利用原字符串的话，就必须扩容，扩容的长度 = 原字符串中空格的个数 *（3-1）。尝试一下直接从字符串起始位置开始遍历，当遇上普通字符时，跳过，当遇到空格时，替换成 ”%20″ 存到原字符串中，但是 ”%20″ 是长度为 3，而空格是一个长度，因此 ”%20″ 会覆盖掉空格后的两个元素，若要避免这种情况发生，就要把空格后的元素先往后移动，这样时间复杂度就是 O(n) 了。因为扩容的空间是在字符串末尾，所以要想利用扩容后的空间避免空间冲突，可以从末尾开始存储，而为了保持字符串的顺序，也要对原字符串从末尾进行遍历。这样就既可以利用原字符串的空间，而且时间复杂度也是 O(n) 了。
    执行过程如下图所示：箭头中的编号表示执行的顺序，只画到了遍历到第一个空格为止，后面过程省略。

实现代码

public class Solution {public String replaceSpace(StringBuffer str) {
        int spaceNum = 0;
        // 计算空格数量
        for(int i=0;i<str.length();i++){if(str.charAt(i)==' '){spaceNum++;}        
        }
        int oldIndex = str.length()-1; // 遍历原字符串时的下标
        int newL = str.length()+spaceNum*2; // 替换空格后字符串的长度
        int newIndex = newL-1;// 新字符串的下标
        str.setLength(newL);// 改变字符串的长度（扩容）for(;oldIndex>=0&&newIndex>=0;oldIndex--){if(str.charAt(oldIndex)==' '){//
                str.setCharAt(newIndex--,'0');
                str.setCharAt(newIndex--,'2');
                str.setCharAt(newIndex--,'%');
            }else{str.setCharAt(newIndex--,str.charAt(oldIndex));
            }
       }
        return str.toString();}
}