0557. Reverse Words in a String III

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Example 2:

Input: s = "God Ding"
Output: "doG gniD"

Constraints:

• 1 <= s.length <= 5 * 104
• s contains printable ASCII characters.
• s does not contain any leading or trailing spaces.
• There is at least one word in s.
• All the words in s are separated by a single space.

Analysis

When seeing space or pointing to the end of the string, we can do a small trick by combining these two cases: adding an extra space at the end and remove it before return.

• Time: $O(n)$
• Space: $O(1)$

Code

With trick:

class Solution {
public:
    string reverseWords(string s) {
        s += ' ';
        for (int i = 0, j = 0; j < s.size(); ++j) {
            if (s[j] == ' ') {
                reverse(s.begin() + i, s.begin() + j);
                i = j + 1;
            }
        }
        s.pop_back();
        return s;
    }
};

Without trick:

class Solution {
public:
    string reverseWords(string s) {
        for (int i = 0, j = 0; j < s.size(); ++j) {
            if (s[j] == ' ') {
                reverse(s.begin() + i, s.begin() + j);
                i = j + 1;
            }
            if (j == s.size() - 1) 
                reverse(s.begin() + i, s.end());
        }
        return s;
    }
};

---

Last update: April 1, 2022