剑指Offer(二)：替换空格

2017年11月20日13:11:09 26 9,082 °C

摘要

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

剑指Offer(二)：替换空格

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

最简单的方法就是从头到尾遍历，但是时间复杂度为O(n^2)。

本文采用一种时间复杂度为O(n)的方法。

我们可以先遍历一次字符串，这样就可以统计出字符串空格的总数，并可以由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。以"We are happy"为例，"We are happy"这个字符串的长度为14（包括结尾符号"\n"），里面有两个空格，因此替换之后字符串的长度是18。

我们从字符串的尾部开始复制和替换。首先准备两个指针，P1和P2，P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾。接下来我们向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。碰到第一个空格之后，把P1向前移动1格，在P2之前插入字符串"%20"。由于"%20"的长度为3，同时也要把P2向前移动3格。

移动示意图：

2、编程实现

C++：

class Solution {
public:
    void replaceSpace(char *str,int length) {
        int i = 0;
        int numSpace =0;
        while(str[i] != '\0')
            {
            if(str[i]==' ')
                numSpace++;
            ++i;
        }
        int newLen = i+numSpace*2;
        for(int j=i;j>=0,newLen>=0;)
        {
            if(str[j]==' ')
                {
                str[newLen--] = '0';
                str[newLen--] = '2';
                str[newLen--] = '%';
            }
            else
                str[newLen--] = str[j];
            j--;
        }
    }
};

class Solution {

public:

void replaceSpace(char *str,int length) {

int i = 0;

int numSpace =0;

while(str[i] != '\0')

{

if(str[i]==' ')

numSpace++;

++i;

}

int newLen = i+numSpace*2;

for(int j=i;j>=0,newLen>=0;)

{

if(str[j]==' ')

{

str[newLen--] = '0';

str[newLen--] = '2';

str[newLen--] = '%';

}

else

str[newLen--] = str[j];

j--;

}

};

Python2.7：

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        return s.replace(' ', '%20')

# -*- coding:utf-8 -*-

class Solution:

# s 源字符串

def replaceSpace(self, s):

# write code here

return s.replace(' ', '%20')

微信公众号

分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。

版权声明：本站原创文章，于2017年11月20日13:11:09，由 Jack Cui 发表，共 605 字。
转载请注明：剑指Offer(二)：替换空格 | Jack Cui

发表评论取消回复

目前评论：26 其中：访客 14 博主 12

裸奔的麻瓜 广东省深圳市联通 3
回复 2018年12月21日下午6:02 沙发
大神，C++代码，扩展长度后，没有分配内存，会不会死机
- Jack Cui Admin 辽宁省沈阳市联通GSM/WCDMA/LTE共用出口
  回复 2018年12月21日下午7:10 1层
  @裸奔的麻瓜不会的。
张敏广东省深圳市电信 3
回复 2019年1月3日下午11:32 板凳
大神，你好，C++代码。我理解的字符串的最后一个字母应该是str[index_orignal-1],但是你的代码中最后一个是str[index_orignal]，字符串最后一个内容不是应该下标减1的么？
- Jack Cui Admin 黑龙江省哈尔滨市联通
  回复 2019年1月4日上午9:21 1层
  @张敏已更新感谢。
大敏广东省深圳市南山区电信 3
回复 2019年1月9日下午10:47 地板
大神，请问一下，C++第11行判断i下标对应的值是否结束后，i递增了一位，那判断是否是空格的不就跳过了第0个了吗？
- Jack Cui Admin 黑龙江省哈尔滨市联通
  回复 2019年1月10日下午3:21 1层
  @大敏输入的时候就已经判断字符串是否为空了。字符串不会为空，这么写可以的。
  - wmy 湖北省武汉市中南财经政法大学 0
    回复 2019年3月13日下午2:45 2层
    @Jack Cui 对于这样的字符串” helloworld”，第十一行会跳过第一个空格，使得空格计算减少了吧
    - Jack Cui Admin 北京市百度网讯科技联通节点
      回复 2019年3月13日下午4:53 3层
      @wmy 不会，i++和++i的区别，i++先赋值再自加。
Irelia 湖南省湘潭市联通 1
回复 2019年2月19日下午10:46 4楼
不用replace，python怎么写
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年2月20日上午9:59 1层
  @Irelia 也是一样的，一个一个字符判断。
  - Irelia 湖南省湘潭市联通 1
    回复 2019年2月20日上午11:01 2层
    @Jack Cui 但我觉得就无法和C++思想一样，从后往前，不增加额外空间（除非函数参数给了列表），如果用python，得定义一个列表来存新字符串，而且是从前往后判断？
    - Jack Cui Admin 北京市百度网讯科技联通节点
      回复 2019年2月21日上午10:04 3层
      @Irelia 字符串追加也是可以的。不用太纠结，这种题不会让你用python写，因为太简单。
Lucas 江苏省苏州市电信 2
回复 2019年2月27日上午11:16 5楼
mac的vs上Debug时访问地址错误，EXC_BAD_ACCESS (code=2, address=，，，编译能通过，运行时Bus error: 10
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年3月13日下午4:52 1层
  @Lucas 没有遇到过。
考研驸马 浙江省杭州市电信 0
回复 2019年7月18日上午11:33 6楼
大神，你好！我想请问下第10行的i为什么没有给初值呀？是因为全局变量自动给初值0吗？
但写的时候给了初值i=0，调试会不通过！有点绕，后来我就把这段代码改成了
for (int i = 0; i < length; i++) {
original_length++;
if (str[i] == ' ')
number_blank++;
}
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年7月18日下午7:42 1层
  @考研驸马代码有问题，已经更改。
康斯坦奇 辽宁省沈阳市东北大学一舍西 0
回复 2019年9月18日上午9:56 7楼
大神，为什么从头到尾遍历，时间复杂度为O(n^2)？我用Python写的从头到尾遍历，时间复杂度应该是O(n):
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
if len(s) == 0:
return ”
string = ”
for i in range(len(s)):
if s[i] == ‘ ‘:
string += ‘%20’
else:
string += s[i]
return string
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年9月18日上午10:42 1层
  @康斯坦奇因为你新开了一个string字符串，用空间换了时间。
  如果要求在原有字符串s上操作，就必须的O(n^2)。
- wind 湖北省移动 0
  回复 2023年12月7日下午5:02 1层
  @康斯坦奇我也感觉想不明白，在原有的字符串上怎么操作？
conser 河南省洛阳市电信 0
回复 2019年9月18日上午9:59 8楼
if(newLen>length)
return;
大佬，感觉你这两句代码没有意义，删不删除都可以过题目！
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年9月18日上午10:43 1层
  @conser 这个是异常处理，就本题而言，删了也可以。
ZX-FLY 上海市联通 1
回复 2019年9月27日上午11:58 9楼
if(newLen>length)
return;
请问加入这段代码后，不相当于只要有空格，还没替换，程序就提前结束程序了吗？有点没懂
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年9月27日下午2:35 1层
  @ZX-FLY 如果满足这个条件，说明有异常，这就是异常捕获，但没做处理。可以去掉。
  - ZX-FLY 上海市联通 1
    回复 2019年9月27日下午2:56 2层
    @Jack Cui 您好，还是有点没太懂。只要有空格，就满足if(newLen>length)的条件。那不相当于只要有空格就异常了？然后return;后的语句都不执行了
    - Jack Cui Admin 北京市百度网讯科技联通节点
      回复 2019年9月27日下午5:12 3层
      @ZX-FLY 这里确实有点问题，直接去掉了。感谢。
打不死的黄妖精 江苏省无锡市移动 1
回复 2020年6月28日下午4:09 10楼
您好，有个问题有些想不明白，这里的字符串定义成char *str，编译也没什么问题，可是你下面的str[newLen–] = ‘0’，这就等于说把str指针指向的字符串中的元素修改了，而这在运行中会造成程序崩溃;，但是使用char str[]就没有这样的问题