您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【Python剑指offer系列】-05. 替换空格

题目链接

剑指 Offer 05. 替换空格 - 力扣(LeetCode) (leetcode-cn.com)

题目描述

实现一个函数,将字符串s中每个空格替换成“%20”.

示例

输入:“We are happy”

输出:“We%20are%20happy”

解题思路一

在Python中字符串是不可变对象,不支持直接对字符串中某个字符进行修改,因此需要额外申请空间来存储转换后的字符串。我们可以初始化一个list,然后从前往后遍历输入字符串中的每个字符,如果字符不是空格,直接append到list中,如果字符是空格,就将“%20”append到list中。最后将list转化为字符串格式返回即可。

由于需要遍历一遍输入的字符串,因此时间复杂度为O(N)。同时新开辟的list使用的也是线性大小的额外空间,空间复杂度为O(N)。

Python实现

class Solution:
    def replaceSpace(self, s: str) -> str:
        l = []
        for i in range(len(s)):
            if s[i] != " ":
                l.append(s[i])
            else:
                l.append("%20")
        return "".join(l)

解题思路二

我们还可以在不建立新串的前提下进行原地修改,这种思路无法用Python实现,因为在Python语言中字符串是不可变对象,扩充原字符串会建立新的字符串对象。java可以用StringBuffer类(一个可变字符串类)来实现。C++语言中字符串为可变类型, 如果面试官想要inplace原地修改,可以用C++实现。

由于需要将一个字符的空格替换为三个字符的“%20”,因此要首先遍历长度为s字符串,得到字符串中有n个空格,那么替换空格后的字符串长度应该为s+2*n,因此我们要首先对原字符串进行扩充。另外在替换时我们利用双指针倒序遍历替换元素,初始指针i指向原字符串的末尾元素,指针j指向新字符的末尾元素。(j一直指向的是接下来要填充的位置。)

如果s[i]不是空格,那么将s[i]的元素赋值给s[j],即执行s[i] = s[j],并且将i和j向左移动一位;如果s[i]是空格,那么就要将[j-2,j]范围内的元素设置为“%20“,i向左移动一位,j向左移动三位。如果i和j满足i==j,说明所有的空格都已经替换完毕(因为最初字符串扩充长度是根据空格个数来计算的),此时跳出遍历循环即可。

遍历统计空格数量时间复杂度为O(N),然后再遍历替换的时间复杂度也为O(N),因此整体算法的时间复杂度为O(N)。由于是原地扩展s的长度,因此空间复杂度为O(1)。

C++实现

class Solution {
public:
    string replaceSpace(string s) {
        int l = s.size();
        int count = 0;
        for (char c: s){
            if (c == ' ')
                count ++;
        }
        s.resize(l+2*count);
        for(int i=l-1,j=s.size()-1; i<j;i--,j--){
            if(s[i]!= ' ')
                s[j] = s[i];
            else{
                s[j] = '0';
                s[j-1] = '2';
                s[j-2] = '%';
                j -= 2;
            }
        }
        return s;
    }
};

附:Python中可以直接用str.replace(oldstr,newstr,max)函数来完成字符串替换,函数会返回替换后的新字符串。如果指定max参数,则替换不超过max次。

参考

面试题05. 替换空格 (字符串修改,清晰图解) - 替换空格 - 力扣(LeetCode) (leetcode-cn.com)

 

 


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进