Tony Feng

M.Sc. in Computer Science

Brown University

Leetcode Python

[剑指Offer] Day 3: String

Authored by Tony Feng

Created on April 14th, 2022

Last Modified on April 14th, 2022

Task 1 - Q05. 替换空格

Question

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

Solution 1

1
2
3


class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(" ", "%20") 

Solution 2

1
2
3


class Solution:
    def replaceSpace(self, s: str) -> str:
        return "%20".join(s.split(" "))

Explanation

Time Complexity: O(N)
Space Complexity: O(N)

Task 2 - Q58,II. 左旋转字符串

Question

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

Solution 1

1
2
3
4
5


class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        s1 = s[0:n]
        s2 = s[n:]
        return s2 + s1

Solution 2

1
2
3
4
5
6
7


class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        res = ""
        for i in range(n, len(s) + n):
            res += s[i % len(s)] 

        return res

Explanation

Solution 2 is less efficient than 1, because additional space are created every time.
Time Complexity: O(N)
Space Complexity: O(N)