How to Reverse Words in a String in Place using C++ std::reverse?

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

Example:
Input: [“t”,”h”,”e”,” “,”s”,”k”,”y”,” “,”i”,”s”,” “,”b”,”l”,”u”,”e”]
Output: [“b”,”l”,”u”,”e”,” “,”i”,”s”,” “,”s”,”k”,”y”,” “,”t”,”h”,”e”]

• A word is defined as a sequence of non-space characters.
• The input string does not contain leading or trailing spaces.
• The words are always separated by a single space.
• Could you do it in-place without allocating extra space?

Reversing a string is quite commonly asked during your interview (mostly online screening). Reversing can be done mostly in place or with allocating space. The words are reversed in a sentence, so that we can first reverse the characters first as this will also reverse the appearance order of the words.

Then, we can scan for the word delimiter which is space, and reverse the characters to make them words again. Luckily, with C++ std::reverse, we can do this easily without re-inventing the wheel.

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

class Solution {
public:
    void reverseWords(vector<char>& str) {
        int n = str.size();
        std:reverse(begin(str), end(str));
        int j, i = 0;
        while (i < n) {
            j = i;
            // finding the word delimiter
            while ((i < n) && (str[i] != ' ')) i ++;
            std::reverse(begin(str) + j, begin(str) + i);
            i ++;
        }
    }
};

class Solution {
public:
    void reverseWords(vector<char>& str) {
        int n = str.size();
        std:reverse(begin(str), end(str));
        int j, i = 0;
        while (i < n) {
            j = i;
            // finding the word delimiter
            while ((i < n) && (str[i] != ' ')) i ++;
            std::reverse(begin(str) + j, begin(str) + i);
            i ++;
        }
    }
};

The std::reverse takes two iterator, the [begin, end) with begin included and end exclusive. It might be implemented as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    void reverseWords(vector<char>& str) {
        int n = str.size();
        reverse(str, 0, n);
        int j, i = 0;
        while (i < n) {
            j = i;
            while ((i < n) && (str[i] != ' ')) i ++;
            reverse(str, j, i);
            i ++;
        }
    }
    
private:
    void reverse(vector<char>& str, int start, int end) {
        for (int i = start; i < (end + start) / 2; ++ i) {
            swap(str[i], str[end - 1 - (i - start)]);
        }
    }        
};

class Solution {
public:
    void reverseWords(vector<char>& str) {
        int n = str.size();
        reverse(str, 0, n);
        int j, i = 0;
        while (i < n) {
            j = i;
            while ((i < n) && (str[i] != ' ')) i ++;
            reverse(str, j, i);
            i ++;
        }
    }
    
private:
    void reverse(vector<char>& str, int start, int end) {
        for (int i = start; i < (end + start) / 2; ++ i) {
            swap(str[i], str[end - 1 - (i - start)]);
        }
    }        
};

For both implementations, the space complexity is O(1) constant as swapping takes in-place and the time complexity is O(N) i.e. two linear scans are required.

–EOF (The Ultimate Computing & Technology Blog) —