问题

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

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

解法一:双指针法

首先扩充数组到每个空格替换成"%20"之后的大小,然后从后向前替换空格,也就是双指针法
为什么要从后向前填充,从前向后填充不行么?
从前向后填充就是Offer-05:替换空格 - 图1的算法了,因为每次添加元素都要将添加元素之后的所有元素向后移动

  1. class Solution {
  2. public String replaceSpace(String s) {
  3. int count = 0;
  4. int oldSize = s.length();
  5. char[] c = s.toCharArray();
  6. for(int i = 0; i < oldSize; i++){
  7. if(c[i] == ' '){
  8. count++;
  9. }
  10. }
  11. char[] array = new char[oldSize + count * 2];
  12. int newSize = array.length;
  13. for (int i = newSize - 1, j = oldSize - 1; j < i ; i--, j--) {
  14. if (c[j] != ' ') {
  15. array[i] = c[j];
  16. } else {
  17. array[i] = '0';
  18. array[i - 1] = '2';
  19. array[i - 2] = '%';
  20. i -= 2;
  21. }
  22. }
  23. return new String(array);
  24. }
  25. }
  26. 输入
  27. "We are happy."
  28. 输出
  29. "\u0000\u0000%20are%20happy."
  30. 预期结果
  31. "We%20are%20happy."

出错出哪了???

解法二:官方解法

由于每次替换从 1 个字符变成 3 个字符,使用字符数组可方便地进行替换。建立字符数组地长度为 s 的长度的 3 倍,这样可保证字符数组可以容纳所有替换后的字符

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

    class Solution {
      public String replaceSpace(String s) {
          int length = s.length();
          char[] array = new char[length * 3];
          int size = 0;
          for (int i = 0; i < length; i++) {
              char c = s.charAt(i);
              if (c == ' ') {
                  array[size++] = '%';
                  array[size++] = '2';
                  array[size++] = '0';
              } else {
                  array[size++] = c;
              }
          }
          String newStr = new String(array, 0, size); //把一个数组array从0取到size
          return newStr;
      }
    }
    
  • 时间复杂度:Offer-05:替换空格 - 图2。遍历字符串 s 一遍

  • 空间复杂度:Offer-05:替换空格 - 图3。额外创建字符数组,长度为 s 的长度的 3 倍