Leetcode 151. Reverse Words in a String
Problem Explanation
Given a string with words separated by one or more spaces, the task is to reverse the order of the words. A word is defined as a sequence of non-space characters. The input string may contain leading or trailing spaces.
For example, if the input string is "the sky is blue"
, the output should be "blue is sky the"
.
The challenge also states that if the string contains multiple spaces between two words, these should be reduced to a single space in the reversed string. Also, your reversed string should not contain leading or trailing spaces.
Additionally, there is an instruction for C programmers to try to solve the problem in-place in O(1) extra space.
Solution Explanation
The algorithm implemented can be defined in three steps:
- Reverse the whole string.
- Reverse each word in the string.
- Remove leading, trailing and extra middle spaces.
Assume we are using the string " I love to code "
for the illustration.
At the end of step 1, the whole string is reversed to give " edoc ot evol I "
.
At the end of step 2, each word is reversed to give " code to love I "
.
Finally, step 3 trims the leading and trailing spaces and ensures only a single space between the words to give "code to love I"
.
Python Solution
1 2python 3class Solution: 4 def reverseWords(self, s: str) -> str: 5 return ' '.join(s.split()[::-1])
Java Solution
1 2java 3public class Solution { 4 public String reverseWords(String s) { 5 s = s.trim(); // Trim leading and trailing spaces 6 String[] words = s.split("\\s+"); // Split by one or more spaces 7 StringBuilder sb = new StringBuilder(); 8 for (int i = words.length - 1; i >= 0; i--) { 9 sb.append(words[i]); 10 if (i != 0) { 11 sb.append(' '); 12 } 13 } 14 return sb.toString(); 15 } 16}
JavaScript Solution
1
2javascript
3class Solution {
4 reverseWords(s) {
5 return s.trim().split(/\s+/).reverse().join(' ');
6 }
7}
C++ Solution
1
2cpp
3class Solution {
4public:
5 string reverseWords(string s) {
6 reverse(s.begin(), s.end()); // Reverse the whole string
7 int n = s.size();
8 int idx = 0;
9 for (int start = 0; start < n; start++) {
10 if (s[start] != ' ') { // Skip spaces
11 if (idx != 0) s[idx++] = ' '; // Insert space
12 int end = start;
13 while (end < n && s[end] != ' ') s[idx++] = s[end++];
14 reverse(s.begin() + idx - (end - start), s.begin() + idx); // Reverse each word
15 start = end;
16 }
17 }
18 s.erase(s.begin() + idx, s.end()); // Remove extra characters
19 return s;
20 }
21};
C# Solution
1
2csharp
3public class Solution {
4 public string ReverseWords(string s) {
5 string[] words = s.Trim().Split(" ");
6 Array.Reverse(words);
7 return String.Join(" ", words.Where(x => !string.IsNullOrWhiteSpace(x))); // Remove extra spaces
8 }
9}
Each solution uses the built-in functions of its respective language for reversing, splitting, and joining strings. Also, extra spaces are removed appropriately.
Python split()
and join()
are used with string slicing for array reversing.
In Java, a StringBuilder
is used to append in the reverse order.
JavaScript uses regex to split the string and the reverse()
function to reverse the array before joining.
In C++, reverse is accomplished using the standard reverse()
function with string iterators.
In C#, Array.Reverse()
is used and then lambda expression and LINQ are used to filter out extra spaces.# Rust Solution
1
2rust
3impl Solution {
4 pub fn reverse_words(s: String) -> String {
5 s.split_whitespace().rev().collect::<Vec<&str>>().join(" ")
6 }
7}
Go Solution
1 2go 3import ( 4 "strings" 5) 6 7func reverseWords(s string) string { 8 words := strings.Fields(s) 9 for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 { 10 words[i], words[j] = words[j], words[i] 11 } 12 return strings.Join(words, " ") 13}
Scala Solution
1 2scala 3object Solution { 4 def reverseWords(s: String): String = { 5 s.split("\\s+").reverse.mkString(" ") 6 } 7}
In Rust, the split_whitespace
function is used to split the string into words, rev
is used to reverse the slice, collect::<Vec<&str>>
is used to convert the slice to a vector, and finally join
is used to combine the words back into a string.
The Go solution uses strings.Fields
to split the string into words. Next, a for loop, which updates from the two ends towards the middle, is used to reverse the slice. Finally, strings.Join
is used to reassemble the words into a single string.
The Scala solution is quite straightforward. It uses split
to break down the string into words and then reverse
to reverse the order of the words. The mkString
method is then used to reassemble the words into a single string.
All these solutions effectively carry out the three steps of the algorithm mentioned earlier, i.e., reverse the whole string, reverse each word, and then remove extra spaces. They demonstrate the versatility and effectiveness of built-in string and array manipulations provided by different programming languages.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.