Solution to Reverse Words in a String by LeetCode
Question: https://oj.leetcode.com/problems/reverse-words-in-a-string/ Question Name: Reverse Words in a String To solve it with Python, it is as simple as one statement.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | 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]) |
But is there a better way? Anyone, who read the excellent book Programming Pearls before, might remember Doug McIlroy’s … Read More »