186 Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example, Given s = "the sky is blue", return "blue is sky the".

Could you do it in-placewithout allocating extra space?

// extra space, O(N)

vector<string> tokenize(const string &fullstring)
{
    vector<string> result;
    stringstream ss(fullstring);
    string temp;

    while (getline(ss, temp, ' ')) {
        result.push_back(temp);
    }

    return result;
}

void reverseWords(string &s)
{
    vector<string> tokens = tokenize(s);

    string final_str;
    final_str.reserve(s.size());

    int front = 0, end = tokens.size() - 1;
    while (front < end) {
        swap(tokens.at(front), tokens.at(end));
        front++; end--;
    }

    s.clear();
    for (string &temp : tokens) {
        s += (temp + ' ');
    }
    s.erase(s.end());
}

int main()
{
    string one1 = "";
    reverseWords(one1);
    cout << one1 << endl;

    string one2 = "a";
    reverseWords(one2);
    cout << one2 << endl;

    string one3 = "a b";
    reverseWords(one3);
    cout << one3 << endl;

    string one = "wow look at all these cool words";
    reverseWords(one);
    cout << one << endl;
}

// in space, O(N)

The basic idea is to first reverse the string entirely once, and then iterate through the reversed string again to reverse every delimited string.

void my_reverse(string &in, int start, int end)
{
    while (start < end) {
        swap(in[start], in[end]);
        start++; end--;
    }
}

void reverseWords(string &s)
{
    reverse(s.begin(), s.end());
    int iter_start = 0;

    for (int i = 0; i < s.length(); i++) {
        if (s[i] == ' ') {
            my_reverse(s, iter_start, i - 1);
            iter_start = i + 1;
        }
    }

    // reverse last word, corner case
    my_reverse(s, iter_start, s.length() - 1);
}