[151]翻转字符串里的单词

//给定一个字符串，逐个翻转字符串中的每个单词。 
//
// 说明： 
//
// 
// 无空格字符构成一个 单词 。 
// 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 
// 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。 
// 
//
// 
//
// 示例 1： 
//
// 输入："the sky is blue"
//输出："blue is sky the"
// 
//
// 示例 2： 
//
// 输入："  hello world!  "
//输出："world! hello"
//解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
// 
//
// 示例 3： 
//
// 输入："a good   example"
//输出："example good a"
//解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
// 
//
// 示例 4： 
//
// 输入：s = "  Bob    Loves  Alice   "
//输出："Alice Loves Bob"
// 
//
// 示例 5： 
//
// 输入：s = "Alice does not even like bob"
//输出："bob like even not does Alice"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 104 
// s 包含英文大小写字母、数字和空格 ' ' 
// s 中 至少存在一个 单词 
// 
//
// 
// 
//
// 
//
// 进阶： 
//
// 
// 请尝试使用 O(1) 额外空间复杂度的原地解法。 
// 
// Related Topics 字符串 
// 👍 288 👎 0

/*
* 151 翻转字符串里的单词
* 2021-03-06 11:18:50
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    string reverseWords(string s) {
        int k = 0;
        for(int i = 0;i < s.size();i++){
            while(i < s.size() && s[i] == ' ') i ++ ; // find word begin == i
            if(i == s.size()) break;
            int j = i;
            while(j < s.size() && s[j] != ' ') j ++; // find word end == j

            reverse(s.begin() + i, s.begin() + j); // reverse
            if(k) s[k++] = ' '; // skip head ' '
            while(i < j) s[k++] = s[i++]; // copy
        }

        s.erase(s.begin() + k, s.end()); // erase end of them
        reverse(s.begin(), s.end()); // reverse
        return s;
    }
};
//leetcode submit region end(Prohibit modification and deletion)