Skip to main content

Reverse Words in a String

Problem​

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.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    string reverseWords(string s) {
        vector<string> words;
        int cnt = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            if (s[i] != ' ')
                cnt++;
            else {
                if (cnt == 0) continue;
                words.push_back(s.substr(i - cnt, cnt));
                cnt = 0;
            }
        }
        if (cnt) {
            words.push_back(s.substr(n - cnt, cnt));
            cnt = 0;
        }
        string w = "";
        reverse(words.begin(), words.end());
        w = words[0];
        for (int i = 1; i < words.size(); i++) {
            w += " " + words[i];
        }
        return w;
    }
};