Reverse Words in a String III

class Solution {
public:
    string reverseWords(string s) {
        int spacePos = -1;
        int strLen = (int)s.size();
        for (int i = 0; i <= strLen; i++) {
            if (i == strLen || s[i] == ' ') {
                int start = spacePos + 1;
                int end = i - 1;
                while (start < end) {
                    char swapTemp = s[start];
                    s[start] = s[end];
                    s[end] = swapTemp;
                    start++;
                    end--;
                }
                spacePos = i;
            }
        }
        return s;
    }
};

The provided C++ code defines a solution to the problem of reversing all the words in a given string s without changing the order of the words. This solution involves iterating over the characters of the string, finding each word by its space boundaries, and reversing it in place.

To achieve this, the method reverseWords uses a loop to process each character in the string until the end is reached. It checks for spaces or the end of the string as delimiters to identify entire words. Once a word is identified (i.e., between positions spacePos + 1 and i - 1), another loop is used to reverse the characters within that word by swapping them iteratively from the start to the end.

• Initialization of variable spacePos to -1 helps in identifying the start of the first word.
• The outer loop runs from the start of the string to one past its end to ensure the last word is included.
• The inner loop swaps characters symmetrically from the outside towards the center of the word, thus reversing their order.
• After processing each word, spacePos is updated to the current position i to start finding the next word.

Finally, the modified string with each word reversed is returned.

This approach is both efficient and concise, utilizing in-place operations for a space complexity of O(1) and a linear time complexity of O(n) where n is the length of the string.

class Solution {
    
    public String reverseEachWord(String input) {
        int spaceIndex = -1;
        char[] characters = input.toCharArray();
        int length = input.length();
        for (int index = 0; index <= length; index++) {
            if (index == length || characters[index] == ' ') {
                int start = spaceIndex + 1;
                int end = index - 1;
                while (start < end) {
                    char swap = characters[start];
                    characters[start] = characters[end];
                    characters[end] = swap;
                    start++;
                    end--;
                }
                spaceIndex = index;
            }
        }
        return new String(characters);
    }
    
}

The Java solution presented solves the problem of reversing each word in a given string individually by treating spaces as word delimiters. The methodology used to achieve this is straightforward and efficient.

• Start by initializing an index to track the latest space encountered (spaceIndex), which begins at -1 to account for the first word.
• Convert the input string into a character array (characters) for easy manipulation of individual characters.
• Loop through each character in the array until the end is reached (index <= length). In each iteration, check if the end of a word is reached, indicated either by a space or the end of the string (index == length || characters[index] == ' ').
• Once the end of a word is identified:
  • Calculate the start (spaceIndex + 1) and end (index - 1) indices for the word within the array.
  • Use a while loop to reverse the characters within these boundaries by swapping characters from start to end until the middle of the word is reached.
  • Update spaceIndex to the current index after reversing the word, setting the stage for the next word.
• After all words are reversed inline within the array, construct and return the new string from the modified character array.

This implementation is efficient, leveraging in-place character swaps within the original array to reverse each word, eliminating the need for additional storage. This process ensures that the overall space complexity remains constant, O(1), apart from the input string's character array. The solution effectively handles edge cases, such as strings with multiple spaces or no spaces, demonstrating robustness suitable for varied inputs, making it a reliable method for reversing words in a string.