前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指offer - 替换空格 - JavaScript

剑指offer - 替换空格 - JavaScript

作者头像
心谭博客
发布2020-04-21 10:49:49
3890
发布2020-04-21 10:49:49
举报
文章被收录于专栏:YuanXin

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

题目描述

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

解法 1:正则表达式

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

代码语言:javascript
复制
// ac地址:https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
// 原文地址:https://xxoo521.com/2019-12-19-ti-huan-kong-ge/
/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    return s.replace(/ /g, "%20");
};

解法 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)。

代码语言:javascript
复制
// ac地址:https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
// 原文地址:https://xxoo521.com/2019-12-19-ti-huan-kong-ge/

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    if (!s || !s.length) {
        return "";
    }

    let emptyNum = 0,
        chNum = 0;
    for (let i = 0; i < s.length; ++i) {
        if (s[i] === " ") {
            ++emptyNum;
        } else {
            ++chNum;
        }
    }

    const length = emptyNum * 2 + chNum;
    const chs = new Array(length);
    // i 是新字符串的下标
    // j 是原字符串的下标
    for (let i = 0, j = 0; j < s.length; ++j) {
        if (s[j] === " ") {
            chs[i++] = "%";
            chs[i++] = "2";
            chs[i++] = "0";
        } else {
            chs[i++] = s[j];
        }
    }

    return chs.join("");
};

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-12-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 解法 1:正则表达式
  • 解法 2:双指针
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档