151. Reverse Words in a String

Posted on Edited on In

151. Reverse Words in a String

Description

Difficulty: Medium

Related Topics: Two Pointers, String

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:

1
2
Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

1
2
3
Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

1
2
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.

Constraints:

  • 1 <= s.length <= 104
  • s contains English letters (upper-case and lower-case), digits, and spaces ' '.
  • There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Hints/Notes

  • Reverse the whole string first, then each word
  • The handling of spaces is the key to AC for this problem
    • The space at the end of the string
    • The extra spaces between the words
    • Use a separate index variable to track the return string

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        int index = 0, len = s.size();
        for (int i = 0; i < len; i++) {
            if (s[i] != ' ') {
                if (index != 0) {
                    s[index++] = ' ';
                }
                int end = i;
                while (s[end] != ' ' && end < len) {
                    s[index++] = s[end++];
                }
                reverse(s.begin() + index - (end - i), s.begin() + index);
                i = end;
            }
        }
        s.erase(s.begin() + index, s.end());
        return s;
    }
};