替换空格

力扣题目链接(opens new window)

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

示例 1： 输入：s = “We are happy.”
输出：”We%20are%20happy.”

思路

如果想把这道题目做到极致，就不要只用额外的辅助空间了！

首先扩充数组到每个空格替换成”%20”之后的大小。

然后从后向前替换空格，也就是双指针法，过程如下：

i指向新长度的末尾，j指向旧长度的末尾。

替换空格

有同学问了，为什么要从后向前填充，从前向后填充不行么？

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

  1. 不用申请新数组。
  2. 从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。

时间复杂度，空间复杂度均超过100%的用户。

img

java代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public String replaceSpace(String s) {
    if(s == null || s.length() == 0){
        return s;
    }
    // 扩容
    StringBuilder sb = new StringBuilder();
    while(char c:s.toCharArray()) {
    	if(c == ' ') {
    		sb.append('   ')
    	}
    }
    int left = s.length()-1;
    s += sb.toString();
    int right = s.length()-1;
    char[] arr = s.toCharArray();
    while(left >= 0) {
        if(arr[left] == ' ') {
            arr[right--] = '0';
            arr[right--] = '2';
            arr[right] = '%';
        } else {
            arr[right] = arr[left];
        }
        left--;
        right--;
    }
    return new String(arr);
    
}