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 Handwaving. Because Python’s string is immutable, I have to implement it with C++.
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 63 64 | class Solution { public: void reverseWords(string &s) { /* Clear the spaces */ int toWrite = 0, toRead = 0; bool preSpace = true; // Clear the heading spaces, and reduce multiple spaces // between two words to a single space. while (toRead < s.size()) { if (s[toRead] == ' ') { if (!preSpace) { s[toWrite++] = s[toRead]; preSpace = true; } } else { s[toWrite++] = s[toRead]; preSpace = false; } toRead += 1; } // If there are tailing spaces, remove them. if (s[toWrite-1] == ' ') toWrite -= 1; s.erase(toWrite, s.size()-toWrite); /* Empty string after removing the spaces. */ if (s.size() == 0) return; /* Begin to do Doug McIlroy's Handwaving. */ // Firstly, we are going to reverse each word. int index = -1, wordBegin = 0, wordEnd = 0; while (++index < s.size()) { if (s[index] == ' ') { // Finish one word. wordEnd = index - 1; reverse(s, wordBegin, wordEnd); } else if (s[index-1] == ' ') { wordBegin = index; } } // Reverse the last word. reverse(s, wordBegin, s.size()-1); // Reverse the whole string. reverse(s, 0, s.size()-1); return; } private: void reverse(string &s, int begin, int end) { /* Reverse all chars in s between begin (inclusive) and end (inclusive). The work is done in place. */ char temp; while (begin < end) { temp = s[begin]; s[begin] = s[end]; s[end] = temp; begin += 1; end -= 1; } return; } }; |
PS: this is my first time to write C++ code under Mac system. It seems that the gcc is not working. I have to use the following command to compile it:
clang++ -std=c++11 -stdlib=libc++ -lc++abi ReverseWordsinaString.cpp