Reverse Words in a String
Problem Description
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.
Example 1:
Input: s = "the sky is blue"
Output: "blue is sky the"
Example 2:
Input: s = " hello world "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: s = "a good example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Constraints:
1 <= s.length <= 104scontains English letters (upper-case and lower-case), digits, and spaces' '.- There is at least one word in
s.
Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?
Solve it on LeetCode
Approaches
1. Using Built-in Functions
Intuition:
This approach leverages built-in language functions to split the string by spaces, remove any empty elements, and reverse the resulting word list. This is straightforward but relies heavily on library functions.
Steps:
- Split the input string by spaces.
- Filter out any empty strings resulting from extra spaces.
- Reverse the list and join the words into a single string with space separation.
Code:
- Time Complexity: O(N), where N is the length of the input string, due to splitting and joining operations.
- Space Complexity: O(N), used by split.
2. Two Pointers with Deque
Intuition:
Using a two-pointer approach along with a deque (double-ended queue) can help manage space efficiently and avoid unnecessary memory allocation beyond what is required to store words. This technique manually traverses the string and accumulates words in reverse order.
Steps:
- Traverse the string from end to start using two pointers to find words.
- Use a deque to efficiently manage the words that should appear first in the result.
- Append words to the front of the deque and join them at the end.
- Time Complexity: O(N), where N is the length of the input string, as we traverse each character once.
- Space Complexity: O(N), used by the deque.
3. Two Pointers: In-place Replacement
Intuition:
This method reverses the entire string first, then reverses each word in place. This technique is more space efficient because the reversal occurs directly within the input string resorted to character arrays.
Steps:
- Reverse the entire character array.
- Reverse each word within the array.
- Clean up any extra spaces resulting from the reversal process.
Code:
- Time Complexity: O(N), where N is the length of the string, due to multiple in-place passes.
- Space Complexity: O(1), as modifications are performed in-place without extra space allocations outside of the input array.