剑指offer – 替换空格 – JavaScript

题目形容

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为 We Are Happy.则经过替换之后的字符串为 We%20Are%20Happy。

解法 1：正则表达式

第一反应一定正则表达式，在真正项目中，一定也会选用正则来做匹配和替换。

// ac地址：https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423// 原文地址：https://xxoo521.com/2019-12-19-ti-huan-kong-ge//** * @param {string} str * @return {string} */function replaceSpace(str) {    return str.replace(/ /g, "%20");}

专注前台与算法的系列干货分享，欢迎关注(???)：
「微信公众号：心谭博客」| xxoo521.com | GitHub

解法 2：双指针

由于字符串是不可变的，所以假如直接采用从头到尾遍历原字符串检查空格，并且做替换。那么每次检查到空格后，都需要重新生成字符串。整个过程时间复杂度是 O(N^2)。

优化的关键：提前计算替换后的字符串的长度，避免每次都对字符串做改动。

整体思路如下：

1. 遍历原字符串，统计空格和非空格字符个数，计算替换后的新字符的长度
2. 准备两个指针，指针 i 指向原字符串，指针 j 指向新字符串
3. i 从头开始遍历原字符串
   • str[i]是非空格，那么将 i 指向的字符放入新字符串的 j 位置。i 和 j 都添加 1。
   • str[i]是空格，那么 j 指向的位置依次填入%20。i 添加 1，j 添加 3。

时间复杂度是 O(N)。由于需要对新字符串开拓容器，空间复杂度是 O(N)。

// ac地址：https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423// 原文地址：https://xxoo521.com/2019-12-19-ti-huan-kong-ge//** * @param {string} str * @return {string} */function replaceSpace(str) {    if (!str || !str.length) {        return "";    }    let emptyNum = 0,        chNum = 0;    for (let i = 0; i < str.length; ++i) {        if (str[i] === " ") {            ++emptyNum;        } else {            ++chNum;        }    }    const length = emptyNum * 2 + chNum;    const chs = new Array(length);    // i 是新字符串的下标    // j 是原字符串的下标    for (let i = 0, j = 0; j < str.length; ++j) {        if (str[j] === " ") {            chs[i++] = "%";            chs[i++] = "2";            chs[i++] = "0";        } else {            chs[i++] = str[j];        }    }    return chs.join("");}

专注前台与算法的系列干货分享，欢迎关注(???)

image