Reverse Words In A String Ii - Leetcode Solution

Problem Statement:

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

Example:

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

Explanation:

• The string is "Let's take LeetCode contest"
• Each word is separated by a space.
• We need to reverse the order of each word.
• The output is "s'teL ekat edoCteeL tsetnoc"

Solution:

Approach:

• First, we will reverse the entire string.
• Then, we will reverse each word of the string.

Code:

class Solution {
public:
    void reverseWords(string &str) {
        
        // reverse the entire string
        reverse(str.begin(), str.end());
        
        int i = 0, j;
        while (i < str.length()) {
            // find the end of word
            j = i;
            while (j < str.length() && str[j] != ' ')
                j++;
            
            // reverse the word
            reverse(str.begin() + i, str.begin() + j);
            
            // move to the next word
            i = j+1;
        }
    }
};

Explanation:

1. We first reverse the entire string. The string becomes "tsetnoc tceoLeK ekat set'L"

2. We then iterate through the string and find the end of each word by searching for a space character. We reverse each word by using the reverse() function in the STL.

3. Finally, we have the reversed words separated by spaces in the correct order. Therefore, we have achieved the required string: "s'teL ekat edoCteeL tsetnoc".

Time Complexity:

Time complexity is O(n) where n is the length of the string.

Space Complexity:

The space required is O(1) since the string is being modified in place.

1