Description
Given an input string, reverse the string word by word.
Example 1:
Input: "the sky is blue"
Output: "blue is sky the"
Example 2:
Input: " hello world! "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: "a good example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Note:
- A word is defined as a sequence of non-space characters.
- Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
- You need to reduce multiple spaces between two words to a single space in the reversed string.
Follow up:
For C programmers, try to solve it in-place in O(1) extra space.
Solutions
1. Two Pointers
# Time: O(n)
# Space: O(n)
class Solution:
def reverseWords(self, s: str) -> str:
arr = list(s)
self.reverse_string(arr, 0, len(arr)-1)
self.reverse_words(arr)
words = self.trim_sides(arr)
res = self.trim_space(words)
return ''.join(res)
def reverse_string(self, arr, l, r):
'''reverse a given string'''
while l < r:
arr[l], arr[r] = arr[r], arr[l]
l += 1
r -= 1
return arr
def reverse_words(self, arr):
'''reverse every words in a string'''
l, r = 0, 0
n = len(arr)
while r < n:
while r < n and not arr[r].isspace():
r += 1
self.reverse_string(arr, l, r - 1)
r += 1
l = r
return arr
def trim_sides(self, arr):
'''str.strip() basically'''
if ''.join(arr).isspace():
return []
l, r = 0, len(arr) - 1
while l < r and arr[l].isspace():
l += 1
while l < r and arr[r].isspace():
r -= 1
return arr[l:r+1]
def trim_space(self, words):
'''remove duplicating space in a word'''
if not words:
return []
res = [words[0]]
n = len(words)
for i in range(1, n):
if res[-1].isspace() and words[i].isspace():
continue
res.append(words[i])
return res
# 25/25 cases passed (72 ms)
# Your runtime beats 6.47 % of python3 submissions
# Your memory usage beats 8.7 % of python3 submissions (14.3 MB)
2. 用上堆或者栈
from collections import deque
class Solution:
def reverseWords(self, s: str) -> str:
queue = []
left, right = 0, len(s) - 1
while left in range(len(s)) and s[left] == ' ':
left += 1
while right in range(len(s)) and s[right] == ' ':
right -= 1
word = ''
for i in range(left, right + 1):
if s[i] != ' ':
word += s[i]
else:
if word: queue.append(word)
word = ''
if word:
queue.append(word)
res = []
while queue:
res.append(queue.pop())
return ' '.join(res)
# 25/25 cases passed (40 ms)
# Your runtime beats 38.87 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.3 MB)
class Solution:
def reverseWords(self, s: str) -> str:
output = ''
stack = []
# point idx to last character
idx = len(s) - 1
if not s:
return ''
# point idx to non-space character
while s[idx] == ' ' and idx >= 0:
idx -=1
if idx < 0:
return ''
# iterate over entire string
while idx >= 0:
while s[idx] != ' ' and idx >= 0:
stack.append(s[idx])
idx -= 1
if output:
output += ' '
while stack:
character = stack.pop()
output += character
while s[idx] == ' ':
idx -= 1
return output
# 25/25 cases passed (52 ms)
# Your runtime beats 12.2 % of python3 submissions
# Your memory usage beats 78.26 % of python3 submissions (13.4 MB)