Reverse Words in a String

Problem Statement

Leetcode - 151. Reverse Words in a 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:

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.

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?

Solution

/** For a word to start, check at a non-space char: * beginning of the string or * last character is space For a word to end, check at each character: * if space, last character is not space * the end of the string with */ class Solution { public: void reverse(string &s, int l, int r) { for (int i = 0; i < (r-l)/2; i++) { int left = l+i; int right = r-i; char temp = s[left]; s[left] = s[right]; s[right] = temp; } } string reverseWords(string s) { vector<pair<int, int>> indices; int l = 0; int n = s.size(); int r; for (int i = 0; i < n; i++) { // start of word if (s[i] != ' ') { // if not space if (i == 0) { // if beginning of the string l = 0; } else if (s[i-1] == ' ') { // last character is not space l = i; } } if (s[i] != ' ') { r = i; } // if this character is space or last character in the string bool endOfWord = false; if (s[i] == ' ') { // if space, last character is not space if (i == 0 || (i > 0 && s[i-1] == ' ')) { continue; } endOfWord = true; } else if (i == n-1) { // not space, end of word anyway endOfWord = true; } if (endOfWord) { indices.push_back({l, r}); // cout << "Found word: " << l << " " << r << "\n"; } } string ans = ""; for (int i = indices.size() - 1; i >= 0; i--) { auto p = indices[i]; string word = ""; for (int j = p.first; j <= p.second; j++) { word += s[j]; } ans += word; // cout << ans << "\n"; if (i != 0) { ans += " "; } } return ans; } };

Umakant Vashishtha

Reverse Words in a String

Problem Statement

Solution