05. 替换空格

来源

https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

题目

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

示例:

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

限制：

0 <= s 的长度 <= 10000

思路

时间复杂度优先的话，js 的字符串有 replace 的方法，可以轻易完成此题目的要求，这里就不讨论了。如果创建一个新的字符串，采用循环+判断的方式，可以写出如下解法。

时间复杂度 O(n), 空间复杂度 O(n)。

解题

/**
 * @param {string} s
 * @return {string}
 */
const replaceSpace = function (s) {
  let res = "";
  for (const el of s) {
    if (el === " ") {
      res += "%20";
    } else {
      res += el;
    }
  }
  return res;
};

思路 2

如果空间复杂度优先的话，由于 js 的字符串是不可修改的，无法表达此题的意图。改下题目，改成数组，即

输入: s = "We are happy.".split("")
输出: "We%20are%20happy.".split("")
且禁止使用splice方法

如果从前往后循环，对于 O(n)个空格，每个需要移动 O(n)个元素，时间复杂度达到了 O(n^2)。

如果改成从后往前循环，需要创建两个指针，一个从原来的结尾开始，一个从结果的结尾开始，遍历原数组，填入新数组。

时间复杂度 O(n), 空间复杂度 O(1)。

在一些问题中，如果从前往后复杂度很高时，可以试试从后往前。

解题 2

/**
 * @param {string} s
 * @return {string}
 */
const replaceSpace = function (s) {
  let count = 0;
  for (const e of s) {
    if (e === " ") {
      count++;
    }
  }
  const olength = s.length;
  const nlength = s.length + count * 2;
  for (let i = olength - 1, j = nlength - 1; i >= 0; i--) {
    if (s[i] === " ") {
      s[j--] = "0";
      s[j--] = "2";
      s[j--] = "%";
    } else {
      s[j] = s[i];
      j--;
    }
  }
  return s;
};

从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch