JZ2 — 替换空格

题目描述

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

题目分析

如果可以开辟新的字符串来进行辅助，那么很简单，大家都会写。
我们这里讨论一下如何直接在原来的字符串上进行修改。

C/C++

主要思路：先遍历一遍，数出空格的个数，计算出总的长度。然后从后向前遍历，调整字符位置。从后向前遍历，每个字符只需要移动一次。时间复杂度为O(n)
注意，使用此函数的前提是str指针开辟的内存空间足够大。

class Solution
{
public:
    void replaceSpace(char *str, int length)
    {
        int count = 0;
        for (int i = 0; i < length; i++)
            if (str[i] == ' ')
                count++;
        int len = length + 2 * count - 1;
        for (int i = length - 1; i >= 0; i--)
        {
            if (str[i] == ' ')
            {
                str[len] = '0';
                str[len - 1] = '2';
                str[len - 2] = '%';
                len -= 3;
            }
            else
            {
                str[len] = str[i];
                len--;
            }
        }
        str[length + 2 * count] = '\0';
    }
};

Java

Java字符串带有很多方法，所以很简单，比如可以直接用String类中的replaceAll方法一行搞定。但String对象本身是不会被改变的，相关的方法只是返回了一个新的String对象。
主要思路：删除空格，然后插入%20

public class Solution {
    public String replaceSpace(StringBuffer str) {
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                str.deleteCharAt(i);
                str.insert(i, "%20");
                i += 2;
            }
        }
        return str.toString();
    }
}