朱晓峰

一只生之无趣死之乏味的丧家之犬

0%

[算法训练]LeetCode 151: 翻转字符串里的单词

Posted on Edited on In

题目

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
给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"
示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。


说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。


进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

Related Topics: 字符串

思路

基础解法

把单词都找出来，插进数组中，然后倒序再用空格连接

python的str.split()函数可以分割多个连续的空白字符，具体思路查看解法1

进阶

根据题意

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

思路很简单，先把每个单词都翻转一遍，最后再把整个字符串再翻转一遍。

我觉得难点是在于考虑边界情况。

代码

解法1

1
2
3
4
5
6
7
8
9
10

class Solution:
	def reverseWords(self, s: str) -> str:
		return " ".join([x.strip() for x in s.split()][::-1])

# s.split() 分割并合并所有的连续空白字符，相当于取出所有的单词
# x.strip() 将上一步的单词trim一下
# [::-1] 倒序
# " ".join(array) 用空格连接

解法2

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
class Solution:
	def reverseWords(self, s: str) -> str:
		# python里用数组模拟C语言的字符串会方便许多
		s = list(s)

		length = len(s)
		if length == 0:
			return ""
		i = 0 # 用于遍历s
		begin = 0 # 单词开始的位置
		cur = 0 # 遍历过程中，翻转后的字符串保存的位置
		while i < length:
			if s[i] == " ":
				i += 1
				continue
			begin = i
			while i < length:
				i += 1
				if i >= length or s[i] == " ":
					s[cur:cur+(i-begin)] = self.reverse(s[begin:i])
					cur += i-begin
					if cur < length:
						s[cur] = " "
						cur += 1
					break
		if cur != 0 and s[cur-1] == " ":
			cur -= 1
		s = s[0:cur]
		return "".join(self.reverse(s))
	def reverse(self, s):
		for k in range(int(len(s)/2)):
			t = s[k]
			s[k] = s[len(s)-1-k]
			s[len(s)-1-k] = t
		return s

如果大家有更好的解法，恳请不吝赐教，谢谢！