剑指Offer-替换空格

2017/3/8 posted in  算法-数据结构  

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

结题思路

这个题目Java开发者可能一下就笑了,so easy啊,一个库函数就解决了。但是,我们还是要尝试去造一下轮子,追求原理。
由于要将空格替换为%20,字符串前后的长度肯定不一样,那么就肯定涉及到了重新申请内存地址。

最简单的思路,我们遍历字符串,发现空格,就将空格后面的字符进行移动,然后继续遍历。这样的做法时间复杂度为O(n2),因为每次都移动了大量的字符。

所以我们提出一个简要的方法,重新申请一个字符串(C/C++中准确的成为字符数组),这个新字符串的长度为原字符串长度+空格个数*2(空格的个数,可以通过一次遍历获得),然后用两个指针变量分别指向两个字符串的首位,然后进行复制,当原字符串指针指向空格时,新字符串插入“%20”,直到末尾。

实现代码

库函数解决:

public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll(" ", "%20");
    }
}

自己过不去版:

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuffer newStr = new StringBuffer();
        
        int i = 0;
        
        while(i<str.length()){
            if(str.charAt(i) != ' '){
                newStr.append(str.charAt(i));
            }else{
                newStr.append("%20");
            }
            i++;
        }
        return newStr.toString();
    }
}