Reverse Words in a String II Solutions in C++

// Source : https://oj.leetcode.com/problems/reverse-words-in-a-string-ii/
// Author : Hao Chen
// Date   : 2015-02-09



#include <ctype.h>
#include <iostream>
#include <string>
using namespace std;


void swap(char &a, char &b) {
    char temp = a;
    a = b;
    b = temp;
}
void reverse(string &s, int begin, int end) {
    while(begin < end) {
        swap(s[begin++], s[end--]);
    }
}
void reverseWords(string &s) {

    if (s.size()<=1) return;

    // reverse the whole string
    reverse(s, 0, s.size()-1);

    // reverse the each word
    for ( int begin=0, i=0; i<=s.size(); i++ ) {
        if ( isblank(s[i]) || s[i] == '\0') {
            reverse(s, begin, i-1);
            begin = i+1;
        }
    }
}


int main(int argc, char** argv)
{
    string s = "the sky is blue";
    if ( argc > 1 ) {
        s = argv[1];
    }
    
    cout << s << endl;
    reverseWords(s);
    cout << s << endl;
    
}

/// Source : https://leetcode.com/problems/reverse-words-in-a-string-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-08-12

#include <iostream>
#include <vector>

using namespace std;

/// Using a Stack to reverse the input
/// Time Complexity: O(len(s))
/// Space Complexity: O(len(s))
class Solution {
public:
    void reverseWords(vector<char>& str) {

        vector<string> stack;
        int start = 0;
        string cur = "";
        for(int i = start; i <= str.size() ;)
            if(i == str.size() || str[i] == ' '){
                stack.push_back(cur);
                start = i + 1;
                i = start;
                cur = "";
            }
            else
                cur += str[i++];

        int index = 0;
        for(int i = stack.size() - 1; i >= 0 ; i --){
            for(int j = 0; j < stack[i].size() ; j ++)
                str[index++] = stack[i][j];
            if(i > 0)
                str[index++] = ' ';
        }
    }
};


void print_vec(const vector<char>& vec){
    for(char c: vec)
        cout << c << " ";
    cout << endl;
}

int main() {

    vector<char> str1 = {'t', 'h', 'e', ' ',
                         's', 'k', 'y', ' ',
                         'i', 's', ' ',
                         'b', 'l', 'u', 'e'};
    Solution().reverseWords(str1);
    print_vec(str1);

    return 0;
}

/// Source : https://leetcode.com/problems/reverse-words-in-a-string-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-08-12

#include <iostream>
#include <vector>

using namespace std;

/// Reverse and then Reverse
/// Time Complexity: O(len(s))
/// Space Complexity: O(1)
class Solution {
public:
    void reverseWords(vector<char>& str) {

        reverse(str, 0, str.size() - 1);
        int start = 0;
        for(int i = start + 1; i <= str.size() ;)
            if(i == str.size() || str[i] == ' '){
                reverse(str, start, i - 1);
                start = i + 1;
                i = start + 1;
            }
            else
                i ++;
    }

private:
    void reverse(vector<char>& s, int start, int end){
        for(int i = start, j = end; i < j; i ++, j --)
            swap(s[i], s[j]);
    }
};


void print_vec(const vector<char>& vec){
    for(char c: vec)
        cout << c << " ";
    cout << endl;
}

int main() {

    vector<char> str1 = {'t', 'h', 'e', ' ',
                         's', 'k', 'y', ' ',
                         'i', 's', ' ',
                         'b', 'l', 'u', 'e'};
    Solution().reverseWords(str1);
    print_vec(str1);

    return 0;
}