问题

请实现一个函数，把字符串 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--) {
  15.             if (c[j] != ' ') {
  16.                 array[i] = c[j];
  17.             } else {
  18.                 array[i] = '0';
  19.                 array[i - 1] = '2';
  20.                 array[i - 2] = '%';
  21.                 i -= 2;
  22.             }
  23.         }
  24.         return new String(array);
  25.     }
  26. }
  28. 输入
  29. "We are happy."
  30. 输出
  31. "\u0000\u0000%20are%20happy."
  32. 预期结果
  33. "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 倍