剑指Offer(05)替换空格

今天是小呆刷题的第 20 天，今天的题目是：剑指 Offer 的第 5 题，替换空格

题目要求

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

示例：

1 2	`输入：s = "We are happy." 输出："We%20are%20happy."`

提示：

0 <= s 的长度 <= 10000

解题思路

这道题其实还是蛮简单的一道题，看过题目后小呆至少能想到三种方法：正则、分割、遍历。

正则

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function (s) {
  return s.replace(/\s/g, '%20')
}

分割

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function (s) {
  return s.split(' ').join('%20')
}

遍历+字符串拼接

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function (s) {
  let ans = ''
  for (let i = 0; i < s.length; i++) {
    if (s[i] === ' ') {
      ans += '%20'
    } else {
      ans += s[i]
    }
  }
  return ans
}

在《剑指 Offer 第 2 版》一书中，作者给出了另一种实现思路。通过计算空格的数量，对字符串的长度进行扩充，然后利用双指针去替换其中的空格。当然因为在 JavaScript 中，字符串无法直接扩充长度，所以还是要进行转换操作，这里我们只学习其中的思路即可。

老规矩，动态辅助理解：

替换空格-双指针算法

双指针

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function (s) {
  let strArr = Array.from(s)
  let count = 0

  for (let i = 0; i < strArr.length; i++) {
    if (strArr[i] === ' ') {
      count++
    }
  }

  let left = strArr.length - 1
  let right = strArr.length + count * 2 - 1

  while (left >= 0) {
    if (strArr[left] === ' ') {
      strArr[right--] = '0'
      strArr[right--] = '2'
      strArr[right--] = '%'
      left--
    } else {
      strArr[right--] = strArr[left--]
    }
  }
  return strArr.join('')
}