Reverse Words in a String
The key idea
A word is a maximal run of non-space characters. Once you split the string into its words (which naturally drops every extra, leading, and trailing space), the whole problem becomes reversing the order of that word list and rejoining with a single space.
Problem
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Constraints
- 1 <= s.length <= 10^4
- s contains English letters (upper and lower case), digits, and spaces ' '.
- There is at least one word in s.
Examples
Input: s = "the sky is blue"
Output: "blue is sky the"
Input: s = " hello world "
Output: "world hello"
Input: s = "a good example"
Output: "example good a"
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Two Pointers problems
- 3SumMEDIUM
- 4SumMEDIUM
- Concatenation of ArrayEASY
- Container With Most WaterMEDIUM
- Is SubsequenceEASY
- Merge Sorted ArrayEASY
- Merge Strings AlternatelyEASY
- Move ZeroesEASY
- Next PermutationMEDIUM
- Remove Duplicates from Sorted ArrayEASY
- Remove Duplicates from Sorted Array IIMEDIUM
- Remove ElementEASY