151_Reverse Words in a String
[medium]
Given an input string, reverse the string word by word.
Note: need to make sure that the string only contains letters and spaces.
Test case 1 (easy)
Input: "the weather is good"
Output: "good is weather the"
Test case 2 (with spaces at the beginning and the end)
Input: " the weather is good "
Output: "good is weather the"
Test case 3 (only spaces in the string)
Input: " "
Output: ""
Test case 4 (empty string)
Input: ""
Output: ""
Test case 5 (more than one space between words)
Input: "the weather is good"
Output: "good is weather the"
Idea 1
extract all words in to a list
reverse the list
join strings in the list with space
Complexity 1
Time:
Space:
Solution 1_v1 (with build-in functions split(), reverse(), join())
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
out = " ".join(reversed(s.split()))
return out
Solution 1_v2 (write split(), use build in reverse(), join())
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
out = []
word = ""
# split the string into a list of words
for i in range(len(s)) :
# if current character is not space, add it to word
# if current character is space,and word is not empty,
# append current word to out and set word to empty
# otherwise, continue with next character
if s[i] != " " :
word += s[i]
elif word != "" :
out.append(word)
word = ""
else :
continue
# if sting is not empty and last character is not space,
# add current word to out
if len(s) > 0 and s[-1] != " " :
out.append(word)
# reverse the list, then join with space
return " ".join(reversed(out))
Idea 2
reverse the entire string
loop over the string, reverse the words, append space after each word, and neglect all the spaces.
Complexity 2
Time:
Space:
Solution 2
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
# current word
word = ""
# output reversed string
out = ""
# reverse input string
s = s[ : :-1]
for i in range(len(s)) :
# For first letter in words except the first word,
# put the current stored word into out, let current word be the current letter.
if s[i] != " " and s[i-1] == " " and word != "":
out += word + " "
word = s[i]
# For all other letters, update current word in a reversed order.
elif s[i] != " " :
word = s[i] + word
# Skip all the spaces.
else :
continue
# store the last word
out += word
return out
Idea 3
reverse the entire string
loop over the string, reverse the words, append space after each word, and neglect all the spaces.
do everything in-place
Complexity 3
Time:
Space:
def reverseWords(s):
"""
:type s: str
:rtype: str
"""
if s == "": return s
s = list(s)
# reverse the input string first
s.reverse()
# reverse each word
start, end = 0, 0
while end < len(s):
if not s[end] == " ":
end += 1
elif start < end:
# just finish one word
s[start:end] = reversed(s[start:end])
end += 1
start = end
elif start == end:
# the string starts with space or
# there are multiple spaces between words
s.pop(end)
if start < end:
# the last word is not reversed yet
s[start:end] = reversed(s[start:end])
if len(s) >= 1 and s[-1] == " ":
# the string ends with space
s.pop()
return "".join(s)
Last updated
Was this helpful?