Reverse Words in a Sentence
Problem Statement
Reverse the order of words in a given sentence (a string of words).
Hint
- Note how the words are separated by whitespaces
Try it yourself
def reverse_words(sentence): # sentence here is a string of words#TODO: Write - Your - Codereturn sentence
Solution
import redef reverse_words(sentence):sentence = re.sub(' +', ' ', sentence.strip())sentence = list(sentence)str_len = len(sentence)str_rev(sentence, 0, str_len - 1)start = 0for end in range(0, str_len + 1):if end == str_len or sentence[end] == ' ':str_rev(sentence, start, end - 1)start = end + 1return ''.join(sentence)def str_rev(_str, start_rev, end_rev):while start_rev < end_rev:_str[start_rev], _str[end_rev] = _str[end_rev], _str[start_rev]start_rev += 1end_rev -= 1s = 'Hello World!'print(s)print(reverse_words(s))
Solution Explanation
Runtime complexity
The runtime complexity of this solution is linear, .
Memory complexity
The memory complexity of this solution is constant, .
Solution Breakdown
The essence of this algorithm is to reverse the words in a string by a two-step method using two pointers, effectively manipulating the string in place. Initially, the entire string is reversed, which correctly repositions the words in reverse order. However, due to this reversal of the string, the corresponding characters of words are also reversed. To correct the order of the characters, iterate through the string, and identify the start and end of each word, considering space as a delimiter between words. Set two pointers at the start and end of the word to reverse the characters within that word. By repeating this process for each word, the method effectively achieves the goal without requiring additional memory.
- Convert the string,
sentence, into a list of characters and store it back insentence. - Get the length of the
sentenceand store it instr_len. - Define a
str_revfunction to reverse the entire list of characterssentence. - Set the
startpointer start to 0 and iterate over the range from 0 tostr_len + 1using the pointerend.- When encountering a space or reaching the end of a word, reverse the characters of the word using the
str_revfunction with sentence,start, andend - 1as arguments. - Update the start pointer
starttoend + 1.
- When encountering a space or reaching the end of a word, reverse the characters of the word using the
- Join the list of characters back into a string using
join(sentence). - Return the reversed string.
Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!
