剑指Offer 05.替换空格

力扣题目链接

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

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

思路

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

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

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

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

替换空格 - 图1

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

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

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

这么做有两个好处：

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

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

替换空格 - 图2

java代码如下：

  1. //使用一个新的对象，复制 str，复制的过程对其判断，是空格则替换，否则直接复制，类似于数组复制
  2. public static String replaceSpace(StringBuffer str) {
  3.         if (str == null) {
  4.             return null;
  5.         }
  6.         //选用 StringBuilder 单线程使用，比较快，选不选都行
  7.         StringBuilder sb = new StringBuilder();
  8.         //使用 sb 逐个复制 str ，碰到空格则替换，否则直接复制
  9.         for (int i = 0; i < str.length(); i++) {
  10.         //str.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
  11.         //if (" ".equals(String.valueOf(str.charAt(i)))){
  12.             if (s.charAt(i) == ' ') {
  13.                 sb.append("%20");
  14.             } else {
  15.                 sb.append(str.charAt(i));
  16.             }
  17.         }
  18.         return sb.toString();
  19.     }
  21. //方式二：双指针法
  22.   public String replaceSpace(String s) {
  23.             if (s == null || s.length() == 0) {
  24.                 return s;
  25.             }
  27.             StringBuffer stringBuffer = new StringBuffer();
  28.             for (int i = 0; i < s.length(); i++) {
  29.                 if (s.charAt(i) == ' ') {
  30.                     // 如果出现空格，就添加2个空格，此时就有三个空间存放%20
  31.                     stringBuffer.append("  ");
  32.                 }
  33.             }
  35.             // 没有空格直接返回
  36.             if (stringBuffer.length() == 0) {
  37.                 return s;
  38.             }
  40.             int left = s.length() - 1; // 指向原始字符串的最后位置
  41.             s += stringBuffer;  // 将s扩容
  42.             int right = s.length() - 1; // 指向扩容后的最后位置
  43.             char[] chars = s.toCharArray();
  45.             while (left >= 0) {
  46.                 if (chars[left] == ' ') {
  47.                     chars[right--] = '0';
  48.                     chars[right--] = '2';
  49.                     chars[right] = '%';
  50.                 } else {
  51.                     chars[right] = chars[left];
  52.                 }
  54.                 left--;
  55.                 right--;
  56.             }
  58.             return String.valueOf(chars);
  59.         }
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)