Reverse Words in a String

class Solution {
public:
    string reverseWords(string str) {
        int start = 0, end = str.length() - 1;
        while (start <= end && str[start] == ' ') ++start;
        while (start <= end && str[end] == ' ') --end;
    
        deque<string> words;
        string currentWord;
    
        while (start <= end) {
            if (str[start] == ' ' && !currentWord.empty()) {
                words.push_front(currentWord);
                currentWord = "";
            } else if (str[start] != ' ') {
                currentWord += str[start];
            }
            ++start;
        }
        words.push_front(currentWord);
    
        string output = "";
        while (!words.empty()) {
            output += words.front();
            words.pop_front();
            if (!words.empty()) {
                output += " ";
            }
        }
        return output;
    }
};

This solution addresses the problem of reversing the words in a given string. The implementation is in C++ and follows a clear series of steps to ensure all words are reversed in order while excluding any leading or trailing whitespace:

• Initialize two pointers, start and end, to navigate and trim the string from the beginning and the end, respectively. This effectively removes any spaces at both ends of the string.
• Use a deque to facilitate efficient front insertion, thus easily reversing the order of words.
• Iterate over the trimmed string, constructing each word and pushing it to the front of the deque whenever a space character is encountered, signaling the end of a word.
• After iterating through the string, check if there's a leftover word to be added to the deque.
• Finally, construct the output string from the deque. While popping from the front of the deque, add spaces between the words only if there are more words to follow.

This method ensures that internal multiple spaces are ignored, processing only meaningful word content. The use of a deque supports O(1) complexity for inserting words at the front, making the solution efficient for longer strings.

class Solution {
    public String reverseWordsInString(String str) {
        int start = 0, end = str.length() - 1;
        // Eliminate leading whitespace
        while (start <= end && str.charAt(start) == ' ') ++start;
    
        // Eliminate trailing whitespace
        while (start <= end && str.charAt(end) == ' ') --end;
    
        ArrayDeque<String> deque = new ArrayDeque();
        StringBuilder currentWord = new StringBuilder();
        // Reverse words using deque
        while (start <= end) {
            char ch = str.charAt(start);
    
            if ((currentWord.length() != 0) && (ch == ' ')) {
                deque.offerFirst(currentWord.toString());
                currentWord.setLength(0);
            } else if (ch != ' ') {
                currentWord.append(ch);
            }
            ++start;
        }
        deque.offerFirst(currentWord.toString());
    
        return String.join(" ", deque);
    }
}

The Java program provides a solution for reversing words in a string, where each word is identified by whitespace. Below, find a breakdown of how this code achieves the desired effect:

• Initialize pointers to manage leading and trailing whitespaces.
• Utilize a deque (double-ended queue) to hold words as they are processed from left to right, but ensure they can be retrieved in reverse order efficiently.
• Use a StringBuilder to construct each word dynamically. This allows for easy manipulation of characters within the word and efficient memory usage when compared to regular string concatenation.
• Iterate through the given string. As characters are examined:
  • If a space character is detected following a word, the formed word is added to the front of the deque. This ensures words are reversed when later concatenated.
  • If the character is not a space, it's appended to the current word being built.

The solution leverages the properties of the deque to add words at the beginning, therefore reversing the order naturally when the words are joined back into a single string at the end. This approach handles leading and trailing spaces and efficiently processes the string in a single forward pass.

void reverseString(char* str, int begin, int terminate) {
    while (begin < terminate) {
        char temporary = str[begin];
        str[begin] = str[terminate];
        str[terminate] = temporary;
        begin++;
        terminate--;
    }
}
    
void stripSpaces(char* str) {
    int readIndex, writeIndex;
    for (readIndex = 0, writeIndex = 0; str[readIndex]; ++readIndex)
        if (str[readIndex] != ' ' || (readIndex > 0 && str[readIndex - 1] != ' ')) str[writeIndex++] = str[readIndex];
    if (writeIndex > 0 && str[writeIndex - 1] == ' ') writeIndex--;
    str[writeIndex] = '\0';
}
    
char* reverseWordsInString(char* str) {
    stripSpaces(str);
    
    int len = strlen(str);
    
    for (int i = 0; i < len / 2; i++) {
        char tempChar = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = tempChar;
    }
    
    int startPos = 0;
    for (int endPos = 0; endPos < len; endPos++) {
        if (str[endPos] == ' ') {
            reverseString(str, startPos, endPos - 1);
            startPos = endPos + 1;
        }
    }
    
    reverseString(str, startPos, len - 1);
    return str;
}

The provided C program features a series of functions designed to reverse the words in a given string while managing excess spaces efficiently. The program is structured into three main parts:

• reverseString(char* str, int begin, int terminate): This function takes three parameters—a string and two integers indicating the start and end positions—and reverses the characters within this range. It achieves this by swapping characters incrementally from the start to the middle of the specified segment.

• stripSpaces(char* str): This function removes any extra spaces from the string. It compacts the string such that no two spaces appear consecutively and also trims trailing spaces at the end. The modifications are performed in-place, using two indices to read and write characters appropriately across the string.

• reverseWordsInString(char* str): This function orchestrates the whole process of reversing words in a string. Initially, it calls stripSpaces to cleanse the input string of undesired spaces. It then reverses the entire string to facilitate the subsequent per-word reversal. After the holistic reversal, it iterates through the string to identify individual words (delimited by spaces) and uses reverseString to revert each word to its original order within the newly reversed context.

Together, these functions allow the entire string to be modified such that words appear in their original order but reversed in position relative to the entire input. Here are examples of function interactions:

• Trimming Excess Spaces: Initially eliminates excessive spaces, leaving only single separators between words and no space at the start or end.

• Full String Reversal: Temporarily reverses the entire string's order to simplify the reorientation of each word.

• Per-word Reversal: Iterates through the reversed string to revert each word back to its correct reading direction.

The program exhibits a blend of space and time efficiency by handling modifications in-place and ensures readability and order of words are maintained. This is particularly useful in contexts where string manipulation needs to preserve logical word order while altering their arrangement.

var reverseStringWords = function (str) {
    let start = 0,
        end = str.length - 1;
    while (start <= end && str.charAt(start) == " ") start++;
    while (start <= end && str.charAt(end) == " ") end--;
    
    let wordsArray = [];
    let currentWord = "";
    
    while (start <= end) {
        if (currentWord.length != 0 && str.charAt(start) == " ") {
            wordsArray.push(currentWord);
            currentWord = "";
        } else if (str.charAt(start) != " ") {
            currentWord += str.charAt(start);
        }
        start++;
    }
    wordsArray.push(currentWord);
    return wordsArray.reverse().join(" ");
};

The given JavaScript function, reverseStringWords, efficiently reverses the words in a given string. Here is a breakdown of how this function operates:

1. Initialize two pointers, start and end, to manage traversal from the beginning and end of the string respectively, ignoring any leading or trailing spaces.

2. Create an empty array wordsArray to hold individual words, and a string currentWord to build each word character by character.

3. Loop through each character in the string, using the start pointer:

   • Check if currentWord is not empty and the current character is a space, indicating the end of a word. Push this word to wordsArray, and reset currentWord.
   • If the current character isn't a space, append it to currentWord.
   • Increment the start pointer after each iteration.

4. After exiting the loop, push the last identified word to wordsArray.

5. Finally, reverse the array of words and join them into a single string with spaces between words.

The returned string from this function is the original string with words in reverse order. This function handles multiple and trailing spaces elegantly, ensuring that the reversed output maintains appropriate word spacing.

from collections import deque
    
class ReverseString:
    def reverse_string_words(self, str_input: str) -> str:
        start, end = 0, len(str_input) - 1
        # Remove leading whitespaces
        while start <= end and str_input[start] == " ":
            start += 1
    
        # Remove trailing whitespaces
        while start <= end and str_input[end] == " ":
            end -= 1
    
        word_list, temp_word = deque(), []
        # Reverse words order
        while start <= end:
            if str_input[start] == " " and temp_word:
                word_list.appendleft("".join(temp_word))
                temp_word = []
            elif str_input[start] != " ":
                temp_word.append(str_input[start])
            start += 1
        word_list.appendleft("".join(temp_word))
    
        return " ".join(word_list)

The Python program you have uses a class ReverseString with a method reverse_string_words to reverse the order of words in a given string while removing any leading or trailing whitespace. The solution employs the following approach:

• First, remove any leading spaces by increasing the start index until a non-space character is found.
• Similarly, decrease the end index to trim trailing spaces.
• Use a deque data structure to store words in reverse order efficiently, along with a temporary list temp_word to build individual words.
• Loop through the characters in the trimmed string:
  • Add words to word_list when a space is encountered, resetting the temp_word after each word.
  • Continue adding characters to temp_word if they are not spaces.
  • Ensure any last word is added to word_list.
• Finally, return the words joined with a single space between them.

This method effectively handles strings with multiple spaces and returns a cleanly formatted string with words in the reverse order of their appearance in the input.