Given an input string, reverse the string word by word.

Example 1:
Input: “the sky is blue”
Output: “blue is sky the”

Example 2:
Input: ” hello world! ”
Output: “world! hello”
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:
Input: “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.

Note:
A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:
For C programmers, try to solve it in-place in O(1) extra space.

Reverse Words using StringStream in C++

In C++, we don’t have easy ways to split a string. However, we can use stringstream to get next word and concatenate the string:

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    string reverseWords(string s) {
        stringstream all(s);
        string word = "", res = "";
        while (all >> word) {
            res = word + " " + res;
        }
        return res.substr(0, res.size() - 1);
    }
};

class Solution {
public:
    string reverseWords(string s) {
        stringstream all(s);
        string word = "", res = "";
        while (all >> word) {
            res = word + " " + res;
        }
        return res.substr(0, res.size() - 1);
    }
};

We can also reverse the entire string, then reverse each word, and finally concatenate them.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    string reverseWords(string s) {          
        std::reverse(begin(s), end(s));
        stringstream all(s);
        string word = "", res = "";
        while (all >> word) {
            std::reverse(begin(word), end(word));
            res = res + " " + word;
        }
        return res.empty() ? "" : res.substr(1);
    }
};

class Solution {
public:
    string reverseWords(string s) {          
        std::reverse(begin(s), end(s));
        stringstream all(s);
        string word = "", res = "";
        while (all >> word) {
            std::reverse(begin(word), end(word));
            res = res + " " + word;
        }
        return res.empty() ? "" : res.substr(1);
    }
};

Using C++ stringstream to parse into words allows us to skip extra whitespaces. The first algorithm is more efficient than the second approach. The first implementation is O(N) time, and O(N) space if we consider string concatenation is O(1) constant runtime e.g. In Java/C#, we can use StringBuilder to achieve O(1) string concatenation.

The second approach has O(N^2) complexity, as we need to reverse each words in a string.

Using Filter in Java to Reverse the words

Java is verbose. We can split the string into array, then we need to use Arrays.stream to apply the filtering, then convert back to Array.

1
2
3
4
5
6
7
8
9

    
class Solution {
    public String reverseWords(String s) {
        var arr = s.split(" ");
        var list = Arrays.stream(arr).filter(x -> !x.isEmpty()).toArray(String[]::new);
        Collections.reverse(Arrays.asList(list));
        return String.join(" ", list);
    }
}

    
class Solution {
    public String reverseWords(String s) {
        var arr = s.split(" ");
        var list = Arrays.stream(arr).filter(x -> !x.isEmpty()).toArray(String[]::new);
        Collections.reverse(Arrays.asList(list));
        return String.join(" ", list);
    }
}

Next, we use Collections.reverse to reverse a List – which we also need to use Arrays.asList to convert an array in Java to List. Then, finally, we use String.join static method to concatenate the words in the array to string.

Using Javascript to Reverse words in a string

Javascript is Modern. We can do easy functional programming in Javascript. And it is fluent and easy.

1
2
3
4
5
6
7

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.trim().split(' ').reverse().filter(x => x.length > 0).join(' ');
};

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.trim().split(' ').reverse().filter(x => x.length > 0).join(' ');
};

Using Python’s Map/Reduce to reverse the words in a string

In Python, it is similar. We use filter (built-in function) that takes a lambda to filter out the empty whitespaces after spliting into words. As filtering returns a generator, we need to convert it to list, then we can reverse it.

1
2
3
4
5

class Solution:
    def reverseWords(self, s: str) -> str:
        arr = list(filter(lambda x: len(x) > 0, s.strip().split(' ')))
        arr.reverse()
        return ' '.join(arr)

class Solution:
    def reverseWords(self, s: str) -> str:
        arr = list(filter(lambda x: len(x) > 0, s.strip().split(' ')))
        arr.reverse()
        return ' '.join(arr)

–EOF (The Ultimate Computing & Technology Blog) —