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])