class Solution:
# @param s, a string
# @return a string
def reverseWords(self, s, method = "Stack"):
methodDic = { "Pythonic" : self.reverseWordsPythonic,
"Recursive" : self.reverseWordsRec,
"Stack" : self.reverseWordsStack,
}
methodFun = methodDic.get(method, None)
if methodFun == None: raise Exception("Require unknown method: " + method)
else: return methodFun(s)
# @param s, a string
# @return a string
def reverseWordsStack(self, s):
''' Solve it with a stack
'''
stack = []
index = 0
while index < len(s):
nextWord = ""
# Skip the spaces
while index < len(s) and s[index] == " ": index += 1
# Extract the next non-space word
while index < len(s) and s[index] != " ":
nextWord += s[index]
index += 1
# Push the word into stack. So that when we pop them out later,
# the order is reversed.
if nextWord != "": stack.append(nextWord)
if len(stack) == 0: # No word is in the s
return ""
else:
result = stack.pop()
while len(stack) != 0: result += " " + stack.pop()
return result
# @param s, a string
# @return a string
def reverseWordsRec(self, s):
''' Solve it in a recursive method
'''
# Reach the end.
if s == "": return ""
firstWord = "" # Find the first word in the remaining content.
index = 0
# Skip the heading spaces.
while index < len(s) and s[index] == " ": index += 1
# Extract the first non-space word.
while index < len(s) and s[index] != " ":
firstWord += s[index]
index += 1
# Recursively get the result for the remaining part.
remaining = self.reverseWordsRec(s[index:])
# This is the last word or the tailing spaces.
if remaining == "": return firstWord
# THis word is not in the last position.
else: return remaining + " " + firstWord
# @param s, a string
# @return a string
def reverseWordsPythonic(self, s):
''' Solve it in a Pythonic way.
'''
return " ".join(s.split()[::-1])