151. Reverse Words in a String
Problem Description
In this problem, we are presented with a string s
that consists of words separated by spaces. Our objective is to reverse the order of these words and return the resulting string with the words placed in opposite order from that of the input. A word is defined as a sequence of non-space characters, meaning that punctuation and letters are considered part of a word but spaces are not. Additionally, the given string s
could have leading or trailing spaces and could also contain multiple spaces between words.
The crux of the problem is to treat the string as a sequence of words rather than individual characters, thus seeing the string as a list where each element is a word. After identifying the words, we need to reverse this list and then reconstruct the string from these reversed words. Importantly, the result must not contain any extra spaces, so only a single space should separate the words, and no leading or trailing spaces should be included.
Intuition
The first solution approach involves using the built-in functions of the language, in this case, Python. Since Python has powerful string manipulation capabilities, we can solve the problem in a few succinct steps. We start by using split()
on the input string s
, which splits the string into a list of words based on spaces while automatically removing any excess spaces. We then reverse this list of words using the reversed()
function. Finally, we join these reversed words back into a string using the join()
function, with a space as the separator. This method is straightforward and efficient, leveraging Python's abilities to handle the reversing and joining of the words with minimal code.
Another approach could use two pointers to iterate over the string and identify the words. This is a bit more manual but doesn't rely on Python's built-in functions as heavily. We would advance the pointers to find the beginning and end of each word, add that word to a list, and once we've gone through the whole string and captured all the words, we would reverse the list of words. We then join these words into a final result string with single spaces between them.
Both methods aim to manipulate the words as a sequence and then reverse that sequence to construct the desired output. Each method has its nuances, but they both focus on the core idea of treating the string as a list of words for the purpose of reversing the order.
Learn more about Two Pointers patterns.
Solution Approach
The reference solution approach provides two potential methods for solving the problem, both involving different use of algorithms, data structures, and language features.
Solution 1: Use Language Built-in Functions
We start by using Python's split()
function, which will iterate through the input string s
and break it into a list of words. This function intelligently ignores any additional spaces beyond the first, so if there is more than one space between words or there are leading and trailing spaces, these won't affect the splitting and won't appear in the final list of words.
Once we have a list of words, we use the reversed()
function, which takes in a sequence and returns an iterator that accesses the given sequence in the reverse order. This is where the reversal of the word order takes place. Since reversed()
returns an iterator, we pass it to the join()
function which concatenates them into a single string with a space as the separator. This gives us the final output.
The time complexity for this approach is O(n)
because split()
and join()
both require a pass through the string or the list of words (which will collectively have a length equivalent to n
, where n
is the length of the string). The space complexity is also O(n)
as we save the list of words separately from the original string.
Solution 2: Two Pointers
While not explicitly implemented here, the two-pointer approach would involve initializing two pointers, usually named i
and j
, which would handle the traversal of the string to identify the start and end of each word. The key steps in this approach would be:
- Initialize
i
andj
to the start of the string. - Increment
j
to find the end of a word, which is indicated by a space or the end of the string. - Extract the word and add it to a result list.
- Reset
i
toj + 1
and find the next word. - After traversing the entire string and capturing all words into the result list, reverse the list.
- Join the reverse list of words as in the first approach.
The two-pointer technique gives you precise control over the traversal and extraction of words, and efficiently manages spaces. It's a common pattern used in string manipulation problems where you need to parse through and process sections of strings based on certain criteria (like non-space characters).
In either case, the goal is the same: to rearrange the words in the string in reverse order while managing and minimizing spaces appropriately. The tools and approaches may vary depending on language features or personal preference, but the underlying logic of word reversal remains central.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the sentence "Hello World from LeetCode"
to illustrate the solution approach using language built-in functions.
-
We start by applying the
split()
function to our example string. This turns our string into a list of words by breaking it at spaces.Input string: "Hello World from LeetCode" After split() function: ["Hello", "World", "from", "LeetCode"]
-
Next, we apply the
reversed()
function to the list of words. This returns an iterator that will go through the words in reverse order.Using reversed() function on our list gives us: ["LeetCode", "from", "World", "Hello"]
-
Finally, we use the
join()
function with a space as a separator to turn our list of reversed words back into a single string.Result after join() function: "LeetCode from World Hello"
By following these steps, we can see that our input string has been transformed such that the words are in the opposite order, and our sentence is grammatically correct without any leading, trailing, or excess in-between spaces.
Now suppose we were to take the two-pointer approach on the example string "Hello World from LeetCode"
, the steps would look something like this:
- Initialize the pointers. In this case, let's call them
start
andend
. - Move
end
forward until it hits a space or the end of the string which signifies the end of a word. - Take the word from
start
toend
and add it to a list.After the first iteration: "Hello" is captured and added to the list. The list of words: ["Hello"]
- Advance
end
to skip any spaces and setstart
to theend
's new location. - Repeat steps 2-4 until the end of the string is reached.
After completing the iterations with capturing: The list of words: ["Hello","World","from","LeetCode"]
- Reverse the list of collected words.
Reversing the list: The list of words: ["LeetCode", "from", "World", "Hello"]
- Join the reversed list with single spaces into a final result string.
Final result: "LeetCode from World Hello"
This example clarifies how both approaches achieve the same result but through different stages of string and list manipulation.
Solution Implementation
1class Solution:
2 def reverseWords(self, s: str) -> str:
3 # Split the input string on spaces to get a list of words
4 words = s.split()
5
6 # Reverse the list of words
7 reversed_words = reversed(words)
8
9 # Join the reversed list of words back into a string with spaces
10 reversed_sentence = ' '.join(reversed_words)
11
12 # Return the reversed sentence
13 return reversed_sentence
14
1class Solution {
2
3 // Method to reverse the words in a given string 's'
4 public String reverseWords(String s) {
5 // Trim the input string to remove leading and trailing whitespaces
6 // and split it into an array of words based on one or more whitespace characters
7 String[] wordsArray = s.trim().split("\\s+");
8
9 // Convert the array of words into a list for easy manipulation
10 List<String> wordsList = new ArrayList<String>(Arrays.asList(wordsArray));
11
12 // Reverse the order of the words in the list
13 Collections.reverse(wordsList);
14
15 // Join the reversed list of words into a single string separated by a single space
16 String reversed = String.join(" ", wordsList);
17
18 // Return the reversed string
19 return reversed;
20 }
21}
22
1#include <algorithm> // Include algorithm header for the std::reverse function
2#include <string> // Include string header for using the std::string class
3
4class Solution {
5public:
6 // This method reverses the words in the string and trims any extra spaces.
7 std::string reverseWords(std::string s) {
8 int start = 0; // Start index of the word
9 int end = 0; // Index used to copy characters
10 int length = s.size(); // Total size of the string
11
12 while (start < length) {
13 // Skip any spaces at the beginning of the current segment.
14 while (start < length && s[start] == ' ') {
15 ++start;
16 }
17
18 if (start < length) {
19 // Put a space before the next word if it's not the first word.
20 if (end != 0) {
21 s[end++] = ' ';
22 }
23 int tempStart = start;
24 // Copy the next word.
25 while (tempStart < length && s[tempStart] != ' ') {
26 s[end++] = s[tempStart++];
27 }
28 // Reverse the word that was just copied.
29 std::reverse(s.begin() + end - (tempStart - start), s.begin() + end);
30 // Move start index to the next segment of the string.
31 start = tempStart;
32 }
33 }
34
35 // Erase any trailing spaces from the string.
36 s.erase(s.begin() + end, s.end());
37 // Reverse the entire string to put the words in the original order.
38 std::reverse(s.begin(), s.end());
39
40 return s; // Return the modified string.
41 }
42};
43
1// Reverses the order of words in a given string.
2function reverseWords(inputString: string): string {
3 // Trim the input string to remove leading and trailing whitespaces.
4 const trimmedString: string = inputString.trim();
5
6 // Split the trimmed string into an array of words using regular expression to match one or more spaces.
7 const wordsArray: string[] = trimmedString.split(/\s+/);
8
9 // Reverse the array of words to get the words in reverse order.
10 const reversedWordsArray: string[] = wordsArray.reverse();
11
12 // Join the reversed words array into a single string, separated by a single space.
13 const reversedString: string = reversedWordsArray.join(' ');
14
15 // Return the reversed string.
16 return reversedString;
17}
18
Time and Space Complexity
The given Python function reverseWords
takes a string s
and reverses the order of the words within it.
Time Complexity:
The time complexity of the function is O(n)
. This is because each operation within the function has a linear time complexity related to the length of the string n
. Here's the breakdown:
s.split()
: This operation traverses the string once and splits it based on spaces, takingO(n)
time.reversed(...)
: Thereversed
function takes an iterable and returns an iterator that goes through the elements in reverse order. This is a linear operation in the number of items to reverse, but since it's just an iterator, the act of reversing itself doesn't consume time for a list, which would rather be encountered during iteration.' '.join(...)
: Joining the words back together involves concatenating them with a space in between, which will also takeO(n)
time because it has to combine all characters back into a single string of approximately the same length as the input.
Since these operations are performed sequentially, the time complexity does not exceed O(n)
.
Space Complexity:
The space complexity is O(n)
as well. This arises from several factors:
s.split()
: This creates a list of all words, which, in the worst case, would be roughlyn/2
(if the string was all single characters separated by spaces), so this consumesO(n)
space.- The list produced by
reversed(...)
: When used withjoin()
, the reversed iterator is realized into a list in memory, therefore an additionalO(n)
space is necessary. - The output string: Since we're creating a new string of approximately the same length as the input, this also requires
O(n)
space.
Since we need to store the intermediate word list and the final string, O(n)
space is the overall space requirement for this function.
Learn more about how to find time and space complexity quickly using problem constraints.
You are given an array of intervals where intervals[i] = [start_i, end_i]
represent the start and end of the ith
interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!