剑指offer 面试题58 - I. 翻转单词顺序（易）& LeetCode 151. 翻转字符串里的单词（易）

字符串与哈希表的应用

Question

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

示例 1： 

1
2
输入: "the sky is blue"
输出: "blue is sky the"
示例 2： 
1
2
3
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3： 
1
2
3
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明： 无空格字符构成一个单词。 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

测试用例

功能测试（句子中有多个单词；句子中只有一个单词）。 特殊输入测试（字符串指针为 nullptr 指针；字符串的内容为空；字符串中只有空格）。

本题考点

考查应聘者的知识迁移能力。当面试的时候遇到第二个问题，而之前我们做过“翻转句子中单词的顺序”这道题目，如果能够把多次翻转字符串的思路迁移过来，就能很轻易地解决字符串左旋转的问题。 考查应聘者对字符串的编程能力。

Intuition

调用Python内建函数方法

  • strip 方法去除字符串前后空格。
  • split 方法以空格分隔字符串，得到words。
  • list表达式去除中间连续的空格。
  • reserve 或 [::-1]，翻转words。
  • join 方法用空格拼接 words。

不调用Python内建函数的方法

  • 单词组装，直到遇到空格，然后入栈。
  • 先入后出的顺序，将单词弹出组成结果返回。

复用 Reverse 函数

第一步翻转句子中所有的字符。比如翻转"I am a student."中所有的字符得到".tneduts amaI"，此时不但翻转了句子中单词的顺序，连单词内的字符顺序也被翻转了。 第二步再翻转每个单词中字符的顺序，就得到了"student a am I"。这正是符合题目要求的输出。

Code

调用Python内建函数方法

1
2
3
4
5
6
7
8
class Solution:
    def reverseWords(self, s: str) -> str:
        if not s:  return ""
        s = s.strip()
        words = s.split(' ')
        words = [word for word in words if word != '']
        words.reverse()
        return " ".join(words)

不调用Python内建函数的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def reverseWords(self, s: str) -> str:
        if not s:  return ""
        stack = []
        
        # 去除开头和结尾的空格
        start = 0
        char = s[start]
        while start < len(s)-1 and char == ' ':
            start += 1
            print(start)
            char = s[start]
        end = len(s)-1
        char = s[end]
        while end >= 0 and char == ' ':
            end -= 1
            char = s[end]
        print(s[start:end+1])

        # 利用栈先入先出的特点完成构建
        tmp = ''
        stack = []
        for i in range(start, end+1):
            char = s[i]
            if char == ' ' and tmp != '':  # 添加and tmp != ''防止连续空格
                # 到达分界位置
                stack.append(tmp)
                tmp = ''
            elif char != ' ':
                tmp += char
        stack.append(tmp)
        print(stack)
        
        # 输出
        res = ''
        while len(stack):
            word = stack.pop()
            res += (word + ' ')
        
        return res[:-1]

复用 Reverse 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def reverseWords(self, s: str) -> str:
        def revse(_str):
            return _str[::-1]
            
        if not s:  return ""
        
        # 去除开头和结尾的空格
        start = 0
        char = s[start]
        while start < len(s)-1 and char == ' ':
            start += 1
            print(start)
            char = s[start]
        end = len(s)-1
        char = s[end]
        while end >= 0 and char == ' ':
            end -= 1
            char = s[end]
        print(s[start:end+1])

        # 第一步翻转句子中所有的字符。比如翻转"I am a student."中所有的字符得到".tneduts amaI"，此时不但翻转了句子中单词的顺序，连单词内的字符顺序也被翻转了。
        s = revse(s[start:end+1])
        # 第二步再翻转每个单词中字符的顺序，就得到了"student a am I"。这正是符合题目要求的输出。
        index = 0
        res = ''
        tmp = ''
        while index < len(s):
            char = s[index]
            if char == ' ' and tmp != '':
                res += revse(tmp) + ' '
                tmp = ''
            elif char != ' ':
                tmp += char
            index += 1
        res += revse(tmp)

        return res

Extension

Question

面试题58 - II. 左旋转字符串

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

示例 1： 

1
2
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2： 
1
2
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
限制：1 <= k < s.length <= 10000

Test Case

功能测试（把长度为n的字符串左旋转0个字符、1个字符、2个字符、n-1个字符、n个字符、n+l个字符）。 特殊输入测试（字符串的指针为 nullptr 指针）。

Intuition

  1. 直接字符串切片
  2. 基于reverse函数的方法，以“abcdefg”为例，我们可以把它分为两部分。由于想把它的前两个字符移到后面，我们就把前两个字符“ab”分到第一部分，把后面的所有字符“cdefg”分到第二部分。我们先分别翻转这两部分，于是就得到“bagfedc”。接下来翻转整个字符串，得到的"cdefgab”刚好就是把原始字符串左旋转两位的结果。

Code

直接字符串切片

1
2
3
4
5
6
7
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        if not s: return ""
        if n > len(s): return s
        font = s[:n]
        back = s[n:]
        return back + font

基于reverse函数的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        def reverse(_str):
            return _str[::-1]

        if not s: return ""
        if n > len(s): return s
        # 以“abcdefg”为例，我们可以把它分为两部分。由于想把它的前两个字符移到后面，我们就把前两个字符“ab”分到第一部分，把后面的所有字符“cdefg”分到第二部分。
        font = s[:n]
        back = s[n:]
        # 我们先分别翻转这两部分，于是就得到“bagfedc”。
        _str = reverse(font) + reverse(back)
        # 接下来翻转整个字符串，得到的"cdefgab”刚好就是把原始字符串左旋转两位的结果。
        _str = reverse(_str)

        return _str

: