151.reverse-words-in-a-string.cpp

/*
 * @lc app=leetcode id=151 lang=cpp
 *
 * [151] Reverse Words in a String
 *
 * https://leetcode.com/problems/reverse-words-in-a-string/description/
 *
 * algorithms
 * Medium (23.19%)
 * Likes:    1568
 * Dislikes: 3194
 * Total Accepted:    512.9K
 * Total Submissions: 2.1M
 * Testcase Example:  '"the sky is blue"'
 *
 * Given an input string s, reverse the order of the words.
 * 
 * A word is defined as a sequence of non-space characters. The words in s will
 * be separated by at least one space.
 * 
 * Return a string of the words in reverse order concatenated by a single
 * space.
 * 
 * Note that s may contain leading or trailing spaces or multiple spaces
 * between two words. The returned string should only have a single space
 * separating the words. Do not include any extra spaces.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: s = "the sky is blue"
 * Output: "blue is sky the"
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: s = "  hello world  "
 * Output: "world hello"
 * Explanation: Your reversed string should not contain leading or trailing
 * spaces.
 * 
 * 
 * Example 3:
 * 
 * 
 * Input: s = "a good   example"
 * Output: "example good a"
 * Explanation: You need to reduce multiple spaces between two words to a
 * single space in the reversed string.
 * 
 * 
 * Example 4:
 * 
 * 
 * Input: s = "  Bob    Loves  Alice   "
 * Output: "Alice Loves Bob"
 * 
 * 
 * Example 5:
 * 
 * 
 * Input: s = "Alice does not even like bob"
 * Output: "bob like even not does Alice"
 * 
 * 
 * 
 * Constraints:
 * 
 * 
 * 1 <= s.length <= 10^4
 * s contains English letters (upper-case and lower-case), digits, and spaces '
 * '.
 * There is at least one word in s.
 * 
 * 
 * 
 * Follow up: Could you solve it in-place with O(1) extra space?
 * 
 */

// @lc code=start
class Solution {
public:
    string reverseWords(string s) {
        int l = 0, r = s.length() - 1;
        while (l < r && s[l] == ' ') ++l;
        while (l < r && s[r] == ' ') --r;
        int i = r, j = r;
        string res;
        while (i >= 0) {
            while (i >= 0 && s[i] != ' ') --i;
            for (int k = i + 1; k <= j; ++k)
                res.push_back(s[k]);
            if (i >= l)
                res.push_back(' ');
            while (i >= 0 && s[i] == ' ') --i;
            j = i;
        }
        return res;
    }
};
// @lc code=end