Reverse Words in a String

http://www.lintcode.com/en/problem/reverse-words-in-a-string/ Given an input string, reverse the string word by word.

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

return "blue is sky the".

Clarification

• What constitutes a word?
  • A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  • Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  • Reduce them to a single space in the reversed string.

Discussion

上面那些clarification questions要能问出来。思路很简单，去掉首尾空格，这个操作在 Valid Number那个题里面也用到了。然后从尾部开始读，读到空格的时候说明要产生一个word了。

class Solution {
public:
    /**
     * @param s : A string
     * @return : A string
     */
    string reverseWords(string s) {
        if(s.empty()) return s;
        int n = s.length();
        //trim leading and traling spaces
        int i = 0;
        while(i<n && ispace(s[i]) == true) {
            i++;
        }
        s.erase(s.begin(), s.begin() + i);
        if(s.length() == 0) return s;
        while(isspace(s.back())) {
            s.pop_back();
        }
        //reverse words
        i = s.length() -1;
        string result = "";
        int len = 0;
        while(i>=0) {
            while(i>=0 && s[i] != ' ') {
                i--;
                len++;
            }
            //after the above while loop, i==-1 || s[i] ==' ' 
            if(s[i] == ' ') {
                result += s.substr(i+1, len) + " ";
            } else { //i==-1, last word in string
                result += s.substr(i+1, len);
            }
            len = 0;
            while(i>=0 && isspace(s[i])) {
                i--;
            }
        }
        return result;
    }
};