Solution: Reverse Words in a String
Let's solve the Reverse Words in a String problem using the Two Pointers pattern.
We'll cover the following
Statement
Given a
Constraints:
The sentence contains English uppercase and lowercase letters, digits, and spaces.
sentence.length
The order of the letters within a word is not to be reversed.
Note: The input string may contain leading or trailing spaces or multiple spaces between words. The returned string, however, should only have a single space separating each word. Do not include any extra spaces.
Solution
The essence of this algorithm is to reverse the words in a string by utilizing a two-step method using two pointers, effectively manipulating the string in place. The entire string is initially reversed, which correctly repositions the words in reverse order. But 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.
Note: The solution mimics an in-place reversal by converting the string to a mutable list of characters, modifying it in place, and then joining it back into a string.
Now let’s look at an example to understand the detailed workflow of this algorithm:
Reverse the entire string: First, we reverse the entire string. This action places the words in the desired order, but each word is itself reversed (i.e., the characters in each word are in the reverse order).
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.