Reverse Words in a String
MedPrompt
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?
Approaches
3 approaches with complexity analysis and trade-offs.
This approach leverages the built-in functions provided by the programming language, such as trim, split, and join, along with collection reversal utilities. It's often the most concise and readable solution for this problem.
Algorithm
- Remove leading and trailing whitespace from the input string
susingtrim(). - Split the trimmed string by one or more spaces (
"\\s+") to get an array of words. - Create a
Listfrom the array of words to use theCollections.reverse()utility. - Reverse the order of elements in the list.
- Join the words in the reversed list with a single space separator using
String.join()to form the final string.
Walkthrough
The simplest way to solve this problem is by using high-level, built-in string and collection manipulation functions. The process is straightforward:
- Trim: The input string
scan have leading or trailing spaces.s.trim()removes these. - Split: The trimmed string is then split into words. The key is to use a regular expression like
"\\s+"as the delimiter, which handles cases with multiple spaces between words, treating them as a single separator. - Reverse: The resulting array of words is converted to a list, which is then reversed using
Collections.reverse(). - Join: Finally,
String.join(" ", words)concatenates the elements of the reversed list into a single string, with each word separated by a single space.
import java.util.Arrays;import java.util.Collections; class Solution { public String reverseWords(String s) { // 1. Trim leading and trailing spaces String trimmedStr = s.trim(); // 2. Split by one or more spaces String[] words = trimmedStr.split("\\s+"); // 3. Reverse the array of words Collections.reverse(Arrays.asList(words)); // 4. Join the words with a single space return String.join(" ", words); }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
Very simple and concise, leading to highly readable code.
Leverages optimized and well-tested library functions, reducing the chance of bugs.
Cons
Creates intermediate data structures (an array of strings and a list), which can consume significant memory, making it O(N) in space complexity.
May not be allowed in interviews that restrict the use of certain built-in functions to test fundamental algorithm knowledge.
Solutions
Solution
public class Solution { public string ReverseWords(string s) { return string.Join(" ", s.Trim().Split(" ").Where(word => !string.IsNullOrEmpty(word) && !string.IsNullOrEmpty(word.Trim())).Reverse()); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.