Home String II | Striver’s SDE Sheet
Post
Cancel

String II | Striver’s SDE Sheet

Problem 1: Reverse Words in a String

You are given a string of length N. You need to reverse the string word by word. There can be multiple spaces between two words and there can be leading or trailing spaces but in the output reversed string you need to put a single space between two words, and your reversed string should not contain leading or trailing spaces.

Worst/Better

Use in built methods and containers like stack, vector.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(n) $

Optimal

Reverse the whole string and then reverse word by word.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        int l = 0, r = 0, i = 0, n = s.size();
        while (i < n) {
            while (i < n && s[i] != ' ')
                s[r++] = s[i++];

            if (l < r) { 
                reverse(s.begin() + l, s.begin() + r);
                if (r == n) break;
                s[r++] = ' ';
                l = r;
            }
            ++i;
        }
        if (r > 0 && s[r-1] == ' ') --r;
        s.resize(r);
        return s;
    }
};

This post is licensed under CC BY 4.0 by the author.

String I | Striver’s SDE Sheet

Binary Tree I | Striver’s SDE Sheet