Solution For Reverse Words In A String

Problem description:
Given a 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.

Solution:
We can solve this problem in two steps:

1. Reverse the entire string
2. Reverse each word in the string

Step 1: Reverse the entire string
We can reverse the entire string by first removing any leading or trailing spaces using the strip() method, and then splitting the string into words using the split() method. We can then join the reversed words using a space separator.

Step 2: Reverse each word in the string
We can reverse each word in the string by iterating over the words in the reversed string and reversing each word using the slice notation.

Code:

“`
class Solution:
def reverseWords(self, s: str) -> str:
# Step 1: Reverse the entire string
s = s.strip().split()
s = ” “.join(reversed(s))

    # Step 2: Reverse each word in the string
    words = s.split(" ")
    for i in range(len(words)):
        words[i] = words[i][::-1]
    return " ".join(words)

“`

Time Complexity: O(n), where n is the length of the input string s.
Space Complexity: O(n), where n is the length of the input string s.

Step by Step Implementation For Reverse Words In A String

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        // reverse the whole string first
        char[] chars = s.toCharArray();
        int i = 0;
        int j = s.length() - 1;
        while (i < j) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
            i++;
            j--;
        }
        // reverse each word
        int start = 0;
        int end = 0;
        while (start < s.length()) {
            // skip spaces
            while (start < s.length() && chars[start] == ' ') {
                start++;
            }
            // find end of word
            end = start;
            while (end < s.length() && chars[end] != ' ') {
                end++;
            }
            // reverse word
            int left = start;
            int right = end - 1;
            while (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
            // move to next word
            start = end;
        }
        return new String(chars);
    }
}

class Solution:
    def reverseWords(self, s: str) -> str:
        # reverse entire string
        s = s[::-1]
        
        # reverse each word in string
        start = 0
        for i in range(len(s)):
            if s[i] == ' ':
                s = s[:start] + s[start:i][::-1] + s[i:]
                start = i + 1
        # reverse last word
        s = s[:start] + s[start:][::-1]
        return s

var reverseWords = function(s) {
    return s.split(' ').reverse().join(' ');
};

class Solution {
public:
    string reverseWords(string s) {
        string res = "";
        int n = s.length();
        int i = 0;
        while(i < n){
            while(i < n && s[i] == ' ') i++; //skip spaces
            if(i == n) break;
            int j = i+1;
            while(j < n && s[j] != ' ') j++; //find end of word
            res = s.substr(i, j-i) + " " + res; //append word to result
            i = j+1;
        }
        return res.substr(0, res.length()-1); //remove trailing space
    }
};

public class Solution { 
    public string ReverseWords(string s) { 
        // first, reverse the whole string 
        char[] charArray = s.ToCharArray(); 
        Array.Reverse(charArray); 
        s = new string(charArray); 
         
        // then, reverse each word in the string 
        int start = 0; 
        for(int i = 0; i < s.Length; i++) { 
            if(s[i] == ' ') { 
                int end = i - 1; 
                while(start < end) { 
                    char temp = s[start]; 
                    s[start] = s[end]; 
                    s[end] = temp; 
                    start++; 
                    end--; 
                } 
                start = i + 1; 
            } 
        } 
         
        // finally, reverse the last word 
        int end = s.Length - 1; 
        while(start < end) { 
            char temp = s[start]; 
            s[start] = s[end]; 
            s[end] = temp; 
            start++; 
            end--; 
        } 
         
        return s; 
    } 
}