剑指offer-05-替换空格

题目描述

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

示例 1:

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

限制:

0 <= s 的长度 <= 10000

题目解析:

在Python和Java等语言中,字符串都被设计成【不可变】的类型,即无法直接修改字符串的某一位字符,需要新建一个字符串实现。

算法流程:
1.初始化一个StringBuilder(java),即为res;
2.遍历列表s中的每个字符c:

  • 当c为空格时:向res后添加字符串"%20";
  • 当c不为空格时,向res后添加字符c;

3.将列表res转化为字符串并返回。

复杂度分析:

  • 时间复杂度 O(N)O(N) : 遍历使用 O(N)O(N) ,每轮添加(修改)字符操作使用 O(1)O(1) ;
  • 空间复杂度 O(N)O(N) : Python 新建的 list 和 Java 新建的 StringBuilder 都使用了线性大小的额外空间。

代码:

class Solution {
    public String replaceSpace(String s) {
                StringBuilder res = new StringBuilder();
        for (Character c: s.toCharArray()
             ) {
            if (c==' '){
                res.append("%20");
            }else res.append(c);
        }
        return res.toString();
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容