剑指Offer05.替换空格 - 图1
参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

题目：剑指Offer 05.替换空格

力扣题目链接

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

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

思路

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

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

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

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

剑指Offer05.替换空格 - 图2

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

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

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

这么做有两个好处：

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

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

剑指Offer05.替换空格 - 图3

C++代码如下：

  1. class Solution {
  2. public:
  3.     string replaceSpace(string s) {
  4.         int count = 0; // 统计空格的个数
  5.         int sOldSize = s.size();
  6.         for (int i = 0; i < s.size(); i++) {
  7.             if (s[i] == ' ') {
  8.                 count++;
  9.             }
  10.         }
  11.         // 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
  12.         s.resize(s.size() + count * 2);
  13.         int sNewSize = s.size();
  14.         // 从后先前将空格替换为"%20"
  15.         for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
  16.             if (s[j] != ' ') {
  17.                 s[i] = s[j];
  18.             } else {
  19.                 s[i] = '0';
  20.                 s[i - 1] = '2';
  21.                 s[i - 2] = '%';
  22.                 i -= 2;
  23.             }
  24.         }
  25.         return s;
  26.     }
  27. };
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

此时算上本题，我们已经做了七道双指针相关的题目了分别是：

拓展

这里也给大家拓展一下字符串和数组有什么差别，

字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定，接下来我来说一说C/C++中的字符串。

在C语言中，把一个字符串存入一个数组时，也把结束符 ‘\0’存入数组，并以此作为该字符串是否结束的标志。

例如这段代码：

  1. char a[5] = "asd";
  2. for (int i = 0; a[i] != '\0'; i++) {
  3. }

在C++中，提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用’\0’来判断是否结束。

例如这段代码:

  1. string a = "asd";
  2. for (int i = 0; i < a.size(); i++) {
  3. }

那么vector< char > 和 string 又有什么区别呢？

其实在基本操作上没有区别，但是 string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有。

所以想处理字符串，我们还是会定义一个string类型。

其他语言版本

C：

  1. char* replaceSpace(char* s){
  2.     //统计空格数量
  3.     int count = 0;
  4.     int len = strlen(s);
  5.     for (int i = 0; i < len; i++) {
  6.         if (s[i] == ' ') {
  7.             count++;
  8.         }
  9.     }
  11.     //为新数组分配空间
  12.     int newLen = len + count * 2;
  13.     char* result = malloc(sizeof(char) * newLen + 1);
  14.     //填充新数组并替换空格
  15.     for (int i = len - 1, j = newLen - 1; i >= 0; i--, j--) {
  16.         if (s[i] != ' ') {
  17.             result[j] = s[i];
  18.         } else {
  19.             result[j--] = '0';
  20.             result[j--] = '2';
  21.             result[j] = '%';
  22.         }
  23.     }
  24.     result[newLen] = '\0';
  26.     return result;
  27. }

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.     }
  26.     //扩充空间，空格数量2倍
  27.     StringBuilder str = new StringBuilder();
  28.     for (int i = 0; i < s.length(); i++) {
  29.         if(s.charAt(i) == ' '){
  30.             str.append("  ");
  31.         }
  32.     }
  33.     //若是没有空格直接返回
  34.     if(str.length() == 0){
  35.         return s;
  36.     }
  37.     //有空格情况 定义两个指针
  38.     int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
  39.     s += str.toString();
  40.     int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
  41.     char[] chars = s.toCharArray();
  42.     while(left>=0){
  43.         if(chars[left] == ' '){
  44.             chars[right--] = '0';
  45.             chars[right--] = '2';
  46.             chars[right] = '%';
  47.         }else{
  48.             chars[right] = chars[left];
  49.         }
  50.         left--;
  51.         right--;
  52.     }
  53.     return new String(chars);
  54. }

Go：

  1. // 遍历添加
  2. func replaceSpace(s string) string {
  3.     b := []byte(s)
  4.     result := make([]byte, 0)
  5.     for i := 0; i < len(b); i++ {
  6.         if b[i] == ' ' {
  7.             result = append(result, []byte("%20")...)
  8.         } else {
  9.             result = append(result, b[i])
  10.         }
  11.     }
  12.     return string(result)
  13. }
  15. // 原地修改
  16. func replaceSpace(s string) string {
  17.     b := []byte(s)
  18.     length := len(b)
  19.     spaceCount := 0
  20.     // 计算空格数量
  21.     for _, v := range b {
  22.         if v == ' ' {
  23.             spaceCount++
  24.         }
  25.     }
  26.     // 扩展原有切片
  27.     resizeCount := spaceCount * 2
  28.     tmp := make([]byte, resizeCount)
  29.     b = append(b, tmp...)
  30.     i := length - 1
  31.     j := len(b) - 1
  32.     for i >= 0 {
  33.         if b[i] != ' ' {
  34.             b[j] = b[i]
  35.             i--
  36.             j--
  37.         } else {
  38.             b[j] = '0'
  39.             b[j-1] = '2'
  40.             b[j-2] = '%'
  41.             i--
  42.             j = j - 3
  43.         }
  44.     }
  45.     return string(b)
  46. }

python：

  1. class Solution:
  2.     def replaceSpace(self, s: str) -> str:
  3.         counter = s.count(' ')
  5.         res = list(s)
  6.         # 每碰到一个空格就多拓展两个格子，1 + 2 = 3个位置存’%20‘
  7.         res.extend([' '] * counter * 2)
  9.         # 原始字符串的末尾，拓展后的末尾
  10.         left, right = len(s) - 1, len(res) - 1
  12.         while left >= 0:
  13.             if res[left] != ' ':
  14.                 res[right] = res[left]
  15.                 right -= 1
  16.             else:
  17.                 # [right - 2, right), 左闭右开
  18.                 res[right - 2: right + 1] = '%20'
  19.                 right -= 3
  20.             left -= 1
  21.         return ''.join(res)
  1. class Solution:
  2.     def replaceSpace(self, s: str) -> str:
  3.         # method 1 - Very rude
  4.         return "%20".join(s.split(" "))
  6.         # method 2 - Reverse the s when counting in for loop, then update from the end.
  7.         n = len(s)
  8.         for e, i in enumerate(s[::-1]):
  9.             print(i, e)
  10.             if i == " ":
  11.                 s = s[: n - (e + 1)] + "%20" + s[n - e:]
  12.             print("")
  13.         return s

javaScript:

  1. /**
  2.  * @param {string} s
  3.  * @return {string}
  4.  */
  5.  var replaceSpace = function(s) {
  6.    // 字符串转为数组
  7.   const strArr = Array.from(s);
  8.   let count = 0;
  10.   // 计算空格数量
  11.   for(let i = 0; i < strArr.length; i++) {
  12.     if (strArr[i] === ' ') {
  13.       count++;
  14.     }
  15.   }
  17.   let left = strArr.length - 1;
  18.   let right = strArr.length + count * 2 - 1;
  20.   while(left >= 0) {
  21.     if (strArr[left] === ' ') {
  22.       strArr[right--] = '0';
  23.       strArr[right--] = '2';
  24.       strArr[right--] = '%';
  25.       left--;
  26.     } else {
  27.       strArr[right--] = strArr[left--];
  28.     }
  29.   }
  31.   // 数组转字符串
  32.   return strArr.join('');
  33. };

TypeScript：

  1. function replaceSpace(s: string): string {
  2.     let arr: string[] = s.split('');
  3.     let spaceNum: number = 0;
  4.     let oldLength: number = arr.length;
  5.     for (let i = 0; i < oldLength; i++) {
  6.         if (arr[i] === ' ') {
  7.             spaceNum++;
  8.         }
  9.     }
  10.     arr.length = oldLength + 2 * spaceNum;
  11.     let cur: number = oldLength - 1;
  12.     for (let i = arr.length - 1; i >= 0; i--, cur--) {
  13.         if (arr[cur] !== ' ') {
  14.             arr[i] = arr[cur]
  15.         } else {
  16.             arr[i] = '0';
  17.             arr[--i] = '2';
  18.             arr[--i] = '%';
  19.         }
  20.     }
  21.     return arr.join('');
  22. };

Swift:

  1. func replaceSpace(_ s: String) -> String {
  2.     var strArr = Array(s)
  3.     var count = 0
  5.     // 统计空格的个数
  6.     for i in strArr {
  7.         if i == " " {
  8.             count += 1
  9.         }
  10.     }
  11.     // left 指向旧数组的最后一个元素
  12.     var left = strArr.count - 1
  13.     // right 指向扩容后数组的最后一个元素（这里还没对数组进行实际上的扩容）
  14.     var right = strArr.count + count * 2 - 1
  16.     // 实际对数组扩容
  17.     for _ in 0..<(count * 2) {
  18.         strArr.append(" ")
  19.     }
  21.     while left < right {
  22.         if strArr[left] == " " {
  23.             strArr[right] = "0"
  24.             strArr[right - 1] = "2"
  25.             strArr[right - 2] = "%"
  26.             left -= 1
  27.             right -= 3
  28.         } else {
  29.             strArr[right] = strArr[left]
  30.             left -= 1
  31.             right -= 1
  32.         }
  33.     }
  35.     return String(strArr)
  36. }

剑指Offer05.替换空格 - 图4