剑指02-替换空格

Posted on | In |

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        temp = ''
        for i in range(len(s)):
            if s[i] != ' ':
                temp += s[i]
            else:
                temp += '%20'
        return temp

c语言的字符串与python中不同，用指针可以更改任意元素，而且其占用字节数可能会有冗余。比如字符串内容是'hello再加上末尾的标志位，至少需要6个字节存储该字符串，然而可能会占用10个字节。如果该字符串里只有一个空格，那么只需要该空格之后的字符由后向前顺序后移2个位，然后把空格替换为%20多占2个字节，仍然没有超过原字符串空间。具体的，先统计空格总数，然后从后往前遍历源字符串的各个字符：

  • 非空格，下标i，前面有sc个空格，后移之后下标是i+2*sc。
  • 空格，下标i，也就是第sc个空格，下标i+2*sc-2、i+2*sc-1和i+2*sc变成'%20'。
  • 直到前面无空格即sc=0。

按照上述思路实现的字符串替换代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        ln = len(s)
        sc = 0 # space count
        for c in s:
            if ' ' == c:
                sc += 1
        if sc == 0:
            return s
        s = [s[i] for i in range(ln)]
        s.extend([' ' for i in range(2*sc)])
        for i in range(ln-1, -1, -1):
            if sc == 0:
                break
            if s[i] == ' ':
                s[i+2*sc-2], s[i+2*sc-1], s[i+2*sc] = '%', '2', '0'
                sc -= 1
            else:
                s[i+2*sc] = s[i]
        return ''.join(s)