难度: Medium
Submission
运行时间: 29 ms
内存: 20.5 MB
class Solution:
def reverseWords(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
def reverse(s, left, right):
while left<right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
reverse(s, 0, len(s)-1)
left=0
for right in range(len(s)):
if s[right] == ' ':
reverse(s, left, right-1)
left = right + 1
reverse(s, left, len(s)-1)
Explain
此题解的主要思路是先对整个字符串数组进行一次完整的反转，然后再逐个反转每个单词以恢复其原始顺序。首先，使用一个辅助函数‘reverse’来实现数组的局部反转。在第一步中，调用这个函数将整个字符串数组从头到尾反转。之后，遍历反转后的数组，每当遇到空格字符时，就反转前一个单词（即从上一个空格后到当前空格前的部分）。对于最后一个单词，因为后面没有空格，所以在循环结束后单独进行反转。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def reverseWords(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
def reverse(s, left, right):
# 用于反转字符串数组s从left到right的部分
while left<right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
# 先反转整个字符串
reverse(s, 0, len(s)-1)
left=0
# 遍历字符串，找到每个单词的界限并反转
for right in range(len(s)):
if s[right] == ' ':
reverse(s, left, right-1)
left = right + 1
# 反转最后一个单词
reverse(s, left, len(s)-1)
Explore
在`reverse`函数中，通过确保传入的`left`和`right`指针始终在有效的数组索引范围内来避免索引越界。函数设计时，调用者需传入有效的起始和结束索引，函数内部通过while循环控制`left`小于`right`条件，确保每次交换都是在合法的范围内。此外，在主函数`reverseWords`中调用`reverse`时，都是基于已确定存在的空格位置或字符串边界，进一步确保了索引的有效性。
选择先整体反转字符串再逐个单词反转的方法，主要是为了方便和效率。整体反转后，原本位于字符串末尾的单词到了开头，但单词内字符的顺序也被反转了。这样只需再逐个反转每个单词内部的字符，就能将整个句子中单词的顺序和每个单词内的字符顺序都恢复到正确状态。这种方法避免了复杂的位置计算，只需要两次扫描：一次全字符串反转，一次遍历单词进行反转，从而提高了算法的效率。
在没有空格的情况下，即整个字符串数组被视为一个单独的单词，算法依然有效。首先，整个字符串被反转，此时由于只有一个单词，所以整个字符串即为单词本身且顺序已经反转。接着，在`reverseWords`函数中，因为找不到空格来标识单词的结束，所以整个字符串只会在最后被单独反转一次。这样，字符串中的字符顺序又被恢复到原始顺序。因此，算法不需要特殊处理这种情况，它自然地处理了只有一个单词的边界情况。