Monday, December 15, 2014

Reverse Words in a String

Q:
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".

T:
To do this in place, we can first reverse the string, then reverse each words.

A:


class Solution {
public:
    void reverseWords(string &s) {
        int l=0;
        int r=s.size()-1;
        while(l < r) {
            char tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
            l++;
            r--;
        }
        l = 0;
        while(l < s.size()) {
            while(s[l] == ' ' && l < s.size()) {
                l++;
            }
            int ll=l;
            while(s[l] != ' ' && l < s.size()) {
                l++;
            }
            int rr=l-1;
            while(ll < rr) {
                char tmp = s[ll];
                s[ll] = s[rr];
                s[rr] = tmp;
                ll++;
                rr--;
            }
            l++;
        }
        l = 0;
        int b = 0;
        while(l< s.size()) {
            while(s[l] == ' ' && l < s.size()) {
                l++;
            }
            while(s[l] != ' ' && l < s.size()) {
                s[b] = s[l];
                b++;
                l++;
            }
            if(l < s.size()-1 && s[l] == ' ') {
                s[b] = ' ';
                b++;
            }
            if(l == s.size()) {
                while(s[b-1]==' ' && b > 0) {
                    b--;
                }
                s = s.substr(0, b);
                return;
            }
        }
    }
};

No comments:

Post a Comment