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:

1. Reverse the whole string.
2. Reverse each word in the string.
3. 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.