A great problem for comprehensive assessment of string manipulation.

151. Reverse Words in a String

LeetCode Problem Link (opens new window)

Given an input string, reverse the string word by word.

Example 1:
Input: "the sky is blue"
Output: "blue is sky the"

Example 2:
Input: " hello world! "
Output: "world! hello"
Explanation: The input string may have leading or trailing spaces, but the output should not have leading or trailing spaces.

Example 3:
Input: "a good example"
Output: "example good a"
Explanation: Reduce multiple spaces between two words to a single space in the reversed string.

Thought Process

This problem is a great way to test various string operations.

Some might solve it using the split library function to separate words and then concatenate them in reverse order using a new string. This would make the problem trivial, losing its intended challenge.

Thus, let's increase the difficulty by not using any auxiliary space, requiring an O(1) space complexity solution.

Without auxiliary space, we must work on the original string directly.

Consider this: by reversing the entire string, the order of words is also reversed, but each word itself is in reverse order. Therefore, reversing each word will correct their order.

Here's the step-by-step solution:

• Remove excessive spaces
• Reverse the entire string
• Reverse each individual word

For example, given the original string: "the sky is blue "

• Remove excessive spaces: "the sky is blue"
• Reverse the string: "eulb si yks eht"
• Reverse each word: "blue is sky the"

Thus, we've successfully reversed the words in the string.

Let's delve into the code implementation details. For instance, with removing excessive spaces some might write the following code:

void removeExtraSpaces(string& s) {
    for (int i = s.size() - 1; i > 0; i--) {
        if (s[i] == s[i - 1] && s[i] == ' ') {
            s.erase(s.begin() + i);
        }
    }
    // Remove trailing spaces
    if (s.size() > 0 && s[s.size() - 1] == ' ') {
        s.erase(s.begin() + s.size() - 1);
    }
    // Remove leading spaces
    if (s.size() > 0 && s[0] == ' ') {
        s.erase(s.begin());
    }
}

The logic is simple: traverse from front to back, erasing spaces as encountered.

While it might initially seem that the above code has O(n) time complexity, the true time complexity is O(n^2) due to erase operations, each being O(n).

Using the two-pointer technique to remove spaces and then resizing the string to the correct size can achieve O(n) time complexity.

// Version 1 
void removeExtraSpaces(string& s) {
    int slowIndex = 0, fastIndex = 0; // Define slow and fast pointers
    // Remove leading spaces
    while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
        fastIndex++;
    }
    for (; fastIndex < s.size(); fastIndex++) {
        // Remove redundant spaces between
        if (fastIndex - 1 > 0
                && s[fastIndex - 1] == s[fastIndex]
                && s[fastIndex] == ' ') {
            continue;
        } else {
            s[slowIndex++] = s[fastIndex];
        }
    }
    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // Remove trailing spaces
        s.resize(slowIndex - 1);
    } else {
        s.resize(slowIndex); // Adjust string size
    }
}

Some might notice that using erase to remove spaces performs reasonably well on LeetCode, mainly due to:

1. The string lengths in the LeetCode test cases are not exceedingly long. If longer, the performance gap would be significant.
2. LeetCode's program runtime measurement isn't always precise.

Version 1 represents a usual thought process: sequentially remove spaces from string's start, middle, and end.

One can draw parallels with the logic in 0027.Remove Element (opens new window), where this problem removes spaces and 0027 removes elements, leading to code written concisely:

// Version 2
void removeExtraSpaces(string& s) {//remove all spaces and add space between adjacent words using fast and slow pointers.
    int slow = 0;   //Overall idea referenced from https://keetcoder.com/problems/0027.remove-element.html
    for (int i = 0; i < s.size(); ++i) { //
        if (s[i] != ' ') { //process when encounter a non-space, i.e., remove all spaces.
            if (slow != 0) s[slow++] = ' '; //manually control space, add space before words except the first word because slow != 0 means it is not the first word.
            while (i < s.size() && s[i] != ' ') { // include the word until encounter a space, meaning the end of the word.
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow); //resize to the size obtained after removing extra spaces.
}

For those who find the above code challenging to understand, it's recommended to first solve 0027.Remove Element (opens new window) or watch a video explanation: Array Elements Removal Isn't Easy! LeetCode: 27 Remove Element (opens new window).

Now, we've implemented the removeExtraSpaces function for removing redundant spaces.

Next, we need to implement reversing string functionality—support reversing sub-strings. These are discussed in 0344.Reverse String (opens new window) and 0541.Reverse String II (opens new window).

Code is as follows:

// Reverse closed interval [start, end] in string s
void reverse(string& s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        swap(s[i], s[j]);
    }
}

Overall code is as follows:

class Solution {
public:
    void reverse(string& s, int start, int end){ //reverse, interval notation: closed interval []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {//remove all spaces and add space between adjacent words, using fast and slow pointers.
        int slow = 0;   //Overall idea referenced from https://keetcoder.com/problems/0027.remove-element.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //process when encountering non-space, i.e., remove all spaces.
                if (slow != 0) s[slow++] = ' '; //manually control space, add space before words except the first word because slow != 0 means it is not the first word.
                while (i < s.size() && s[i] != ' ') { // include the word until encountering a space, meaning the end of the word.
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //resize to the size obtained after removing extra spaces.
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //Remove extra spaces, ensuring only one space between words and none at string start and end.
        reverse(s, 0, s.size() - 1);
        int start = 0; //The first word's starting index is guaranteed to be 0 after removeExtraSpaces.
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //Reached a space or string end indicates the end of a word. Reverse.
                reverse(s, start, i - 1); //reverse, note that is a closed interval [] reverse.
                start = i + 1; //update the next word's start index
            }
        }
        return s;
    }
};

• Time Complexity: O(n)
• Space Complexity: O(1) or O(n), depending on whether the language's string is immutable

Other Language Versions

Java:

class Solution {
   /**
     * Implement without using Java built-in methods
     * <p>
     * 1. Remove excessive spaces from the beginning, end, and middle
     * 2. Reverse the entire string
     * 3. Reverse each word
     */
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1. Remove excessive spaces
        StringBuilder sb = removeSpace(s);
        // 2. Reverse the entire string
        reverseString(sb, 0, sb.length() - 1);
        // 3. Reverse each word
        reverseEachWord(sb);
        return sb.toString();
    }

    private StringBuilder removeSpace(String s) {
        // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }

    /**
     * Reverse the specified range[start, end] in the string
     */
    public void reverseString(StringBuilder sb, int start, int end) {
        // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
        // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

//Solution Two: Create and fill a new character array. Time complexity O(n)
class Solution {
    public String reverseWords(String s) {
        //Source character array
        char[] initialArr = s.toCharArray();
        //New character array
        char[] newArr = new char[initialArr.length+1];//afterwards loop adds "word ", the final trailing space will not be returned
        int newArrPos = 0;
        //i to traverse in reverse order over the source character array
        int i = initialArr.length-1;
        while(i>=0){
            while(i>=0 && initialArr[i] == ' '){i--;}  //Skip spaces
            //now i position is boundary or != space, first record current index, then the inner while is used to determine the first letter of the word
            int right = i;
            while(i>=0 && initialArr[i] != ' '){i--;} 
            //Extract words from the specified range (since i is one position before the first letter, so here +1,), each extracted group comes with a space at the end
            for (int j = i+1; j <= right; j++) {
                newArr[newArrPos++] = initialArr[j];
                if(j == right){
                    newArr[newArrPos++] = ' ';//space
                }
            }
        }
        //If the original string has no words, return an empty string; if there are words, return the character array (converted to String) in the range 0-final whitespace index
        if(newArrPos == 0){
            return "";
        }else{
            return new String(newArr,0,newArrPos-1);
        }
    }
}

//Solution Three: Two reversals + shifts, String's toCharArray() method internally new a char array with the same size as the original string, space complexity: O(n)
class Solution {
    /**
     * Idea:
     *	①Reverse the string  "the sky is blue " => " eulb si yks eht"
     *	②Traverse " eulb si yks eht", reverse and then shift each word
     *	   Here, use the first word as demonstration: " eulb si yks eht" ==reverse=> " blue si yks eht" ==shift=> "blue si yks eht"
     */
    public String reverseWords(String s) {
        //Step 1: Reverse the whole string (at this point, the words within are also reversed)
        char[] initialArr = s.toCharArray();
        reverse(initialArr, 0, s.length() - 1);
        int k = 0;
        for (int i = 0; i < initialArr.length; i++) {
            if (initialArr[i] == ' ') {
                continue;
            }
            int tempCur = i;
            while (i < initialArr.length && initialArr[i] != ' ') {
                i++;
            }
            for (int j = tempCur; j < i; j++) {
                if (j == tempCur) { //Step 2: reverse
                    reverse(initialArr, tempCur, i - 1);//reverse the specified range, without reversing, traversing backwards to fill one by one has a problem
                }
                //Step 3: shift operation
                initialArr[k++] = initialArr[j];
                if (j == i - 1) { //Traversal ends
                    //Avoid out-of-bounds, for example => "asdasd df f", without adding judgment, the last one will by array out-of-bounds
                    if (k < initialArr.length) {
                        initialArr[k++] = ' ';
                    }
                }
            }
        }
        if (k == 0) {
            return "";
        } else {
            //Parameter three: to prevent situations like "asdasd df f"=>"f df asdasd" just full without needing to omit spaces
            return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1);
        }
    }

    public void reverse(char[] chars, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--) {
            chars[i] ^= chars[j];
            chars[j] ^= chars[i];
            chars[i] ^= chars[j];
        }
    }
}

/*
 * Solution Four: Time complexity O(n)
 * Reference the three-step process in Carl's C++ code: first remove excessive spaces, then reverse the entire string, finally reverse each word
 * Unlike Solution One: does not use StringBuilder but operates on String's char[] array to implement the three steps above
 */
class Solution {
    //Implement String's removeExtraSpaces, reverse operations using char[]
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        //1. remove leading and trailing along with middle excessive spaces
        chars = removeExtraSpaces(chars);
        //2. reverse the whole string
        reverse(chars, 0, chars.length - 1);
        //3. reverse each word
        reverseEachWord(chars);
        return new String(chars);
    }

    //1. Use slow and fast pointers to remove leading, trailing, and middle excessive spaces, can refer to array element removal solution
    public char[] removeExtraSpaces(char[] chars) {
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            //first remove all spaces with fast
            if (chars[fast] != ' ') {
                //add space with slow. 
                if (slow != 0)
                    chars[slow++] = ' ';
                //fast encountering a space or reaching the end of the string proves that a word has been iterated
                while (fast < chars.length && chars[fast] != ' ')
                    chars[slow++] = chars[fast++];
            }
        }
        //equivalent to c++'s resize()
        char[] newChars = new char[slow];
        System.arraycopy(chars, 0, newChars, 0, slow); 
        return newChars;
    }

    //Two pointers to reverse designated ranges in a string, can refer to the string reverse solution
    public void reverse(char[] chars, int left, int right) {
        if (right >= chars.length) {
            System.out.println("set a wrong right");
            return;
        }
        while (left < right) {
            chars[left] ^= chars[right];
            chars[right] ^= chars[left];
            chars[left] ^= chars[right];
            left++;
            right--;
        }
    }

    //3. reverse each word
    public void reverseEachWord(char[] chars) {
        int start = 0;
        //end <= s.length() here =, is to make end always point one position after the end of the word, easier to set parameters for reverse
        for (int end = 0; end <= chars.length; end++) {
            // end is each time to the space after the word or end of the string, start reversing word
            if (end == chars.length || chars[end] == ' ') {
                reverse(chars, start, end - 1);
                start = end + 1;
            }
        }
    }
}

Python:

(Version One) First delete whitespace, then reverse the whole, finally reverse words. Because a string is an immutable type, the words need to be converted into a list during the reversal, then join function is used to turn it back into a string, so the space complexity isn't O(1)

class Solution:
    def reverseWords(self, s: str) -> str:
        # Reverse the entire string
        s = s[::-1]
        # Split the string into words, and reverse each word
        # The split() function can automatically ignore extra whitespace
        s = ' '.join(word[::-1] for word in s.split())
        return s

(Version Two) Using two pointers

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split() # type(words) --- list
        words = words[::-1] # Reverse words
        return ' '.join(words) # Convert list into a string

(Version Three) Splitting the string + reversing the list

class Solution:
    def reverseWords(self, s):
        words = s.split() 
        words = words[::-1]
        return ' '.join(words)

(Version Four) After converting the string into a list, using two pointers to remove spaces

class Solution:
    def single_reverse(self, s, start: int, end: int):
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

    def reverseWords(self, s: str) -> str:
        result = ""
        fast = 0
        # 1. First reverse the original string and remove spaces, and add them to the new string
        # Since strings are immutable in Python, convert them to lists for processing
        s = list(s)
        s.reverse()
        while fast < len(s):
            if s[fast] != " ":
                if len(result) != 0:
                    result += " "
                while s[fast] != " " and fast < len(s):
                    result += s[fast]
                    fast += 1
            else:
                fast += 1
        # 2. Then reverse each word in the string
        slow = 0
        fast = 0
        result = list(result)
        while fast <= len(result):
            if fast == len(result) or result[fast] == " ":
                self.single_reverse(result, slow, fast - 1)
                slow = fast + 1
                fast += 1
            else:
                fast += 1

        return "".join(result)

(Version Five) Whenever a space is encountered, it indicates that the previous is a word, so it is added to an array.

class Solution:
    def reverseWords(self, s: str) -> str:
        words = []
        word = ''
        s += ' ' # Helps in processing the last word

        for char in s:
            if char == ' ': # Encountering a space indicates the previous may be a word
                if word != '': # Confirm it is a word, add it to an array
                    words.append(word)
                    word = '' # Clear the current word
                continue
            
            word += char # Collect letters of the word
        
        words.reverse()
        return ' '.join(words)

Go:

Version One:

func reverseWords(s string) string {
    b := []byte(s)

    // Remove leading, middle, and trailing excessive spaces
    slow := 0
    for i := 0; i < len(b); i++ {
        if b[i] != ' ' {
            if slow != 0 {
                b[slow] = ' '
                slow++
            }
            for i < len(b) && b[i] != ' ' { // Copy logic
                b[slow] = b[i]
                slow++
                i++
            }
        }
    }
    b = b[0:slow]
    
    // Reverse the entire string
    reverse(b)
    // Reverse each word
    last := 0
    for i := 0; i <= len(b); i++ {
        if i == len(b) || b[i] == ' ' {
            reverse(b[last:i])
            last = i + 1
        }
    }
    return string(b)
}

func reverse(b []byte) {
    left := 0
    right := len(b) - 1
    for left < right {
        b[left], b[right] = b[right], b[left]
        left++
        right--
    }
}

Version Two:

import (
	"fmt"
)

func reverseWords(s string) string {
	//1. Use double pointers to remove redundant spaces
	slowIndex, fastIndex := 0, 0
	b := []byte(s)
	//Remove leading excess space
	for len(b) > 0 && fastIndex < len(b) && b[fastIndex] == ' ' {
		fastIndex++
	}
    //Remove redundant spaces between words
	for ; fastIndex < len(b); fastIndex++ {
		if fastIndex-1 > 0 && b[fastIndex-1] == b[fastIndex] && b[fastIndex] == ' ' {
			continue
		}
		b[slowIndex] = b[fastIndex]
		slowIndex++
	}
	//Remove trailing excess space
	if slowIndex-1 > 0 && b[slowIndex-1] == ' ' {
		b = b[:slowIndex-1]
	} else {
		b = b[:slowIndex]
	}
	//2. Reverse the entire string
	reverse(b)
	//3. Reverse individual words  i: start of word, j: end of word
	i := 0
	for i < len(b) {
		j := i
		for ; j < len(b) && b[j] != ' '; j++ {
		}
		reverse(b[i:j])
		i = j
		i++
	}
	return string(b)
}

func reverse(b []byte) {
    left := 0
    right := len(b) - 1
    for left < right {
        b[left], b[right] = b[right], b[left]
        left++
        right--
    }
}

//Double pointer solution. Reverse traversal on the pointer, putting the traversed words (separated by spaces to differentiate) in order into extra space
//Time complexity O(n), space complexity O(n)
func reverseWords(s string) string {
    strBytes := []byte(s)
    n := len(strBytes)
    // Record the start and end position of the valid character range
    start, end := 0, n-1
    // Remove leading spaces
    for start < n && strBytes[start] == 32 {
        start++
    }
    // Handle cases where all are spaces or an empty string
    if start == n {
        return ""
    }
    // Remove trailing spaces
    for end >= 0 && strBytes[end] == 32 {
        end--
    }
    // Result slice, pre-allocate capacity
    res := make([]byte, 0, end-start+1)
    // Traverse the valid character range from back to front
    for i := end; i >= start; {
        // Find the start position of the word by directly checking loop conditions
        for ; i >= start && strBytes[i] == 32; i-- {
        }
        j := i
        for ; j >= start && strBytes[j]!= 32; j-- {
        }
        res = append(res, strBytes[j+1:i+1]...)
        // Add space only when it is not the last word
        if j > start {
            res = append(res, 32)
        }
        i = j
    }
    return string(res)
}

JavaScript:

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
   // Convert string to an array
   const strArr = Array.from(s);
   // Remove excessive spaces
   removeExtraSpaces(strArr);
   // Reverse
   reverse(strArr, 0, strArr.length - 1);

   let start = 0;

   for(let i = 0; i <= strArr.length; i++) {
     if (strArr[i] === ' ' || i === strArr.length) {
       // Reverse word
       reverse(strArr, start, i - 1);
       start = i + 1;
     }
   }

   return strArr.join('');
};

// Remove excessive spaces
function removeExtraSpaces(strArr) {
  let slowIndex = 0;
  let fastIndex = 0;

  while(fastIndex < strArr.length) {
    // Remove leading and repeated spaces
    if (strArr[fastIndex] === ' ' && (fastIndex === 0 || strArr[fastIndex - 1] === ' ')) {
      fastIndex++;
    } else {
      strArr[slowIndex++] = strArr[fastIndex++];
    }
  }

  // Remove trailing spaces
  strArr.length = strArr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex;
}

// Reverse characters from start to end in strArr
function reverse(strArr, start, end) {
  let left = start;
  let right = end;

  while(left < right) {
    // Swap
    [strArr[left], strArr[right]] = [strArr[right], strArr[left]];
    left++;
    right--;
  }
}

TypeScript:

function reverseWords(s: string): string {
    /** Utils **/
    // Remove excessive spaces, e.g. '   hello     world   ' => 'hello world'
    function delExtraSpace(arr: string[]): void {
        let left: number = 0,
            right: number = 0,
            length: number = arr.length;
        while (right < length && arr[right] === ' ') {
            right++;
        }
        while (right < length) {
            if (arr[right] === ' ' && arr[right - 1] === ' ') {
                right++;
                continue;
            }
            arr[left++] = arr[right++];
        }
        if (arr[left - 1] === ' ') {
            arr.length = left - 1;
        } else {
            arr.length = left;
        }
    }
    // Reverse string, e.g. 'hello' => 'olleh'
    function reverseWords(strArr: string[], start: number, end: number) {
        let temp: string;
        while (start < end) {
            temp = strArr[start];
            strArr[start] = strArr[end];
            strArr[end] = temp;
            start++;
            end--;
        }
    }

    /** Main code **/
    let strArr: string[] = s.split('');
    delExtraSpace(strArr);
    let length: number = strArr.length;
    // Reverse the entire string
    reverseWords(strArr, 0, length - 1);
    let start: number = 0,
        end: number = 0;
    while (start < length) {
        end = start;
        while (strArr[end] !== ' ' && end < length) {
            end++;
        }
        // Reverse individual words
        reverseWords(strArr, start, end - 1);
        start = end + 1;
    }
    return strArr.join('');
};

Swift:

func reverseWords(_ s: String) -> String {
    var stringArr = removeSpace(s)
    reverseString(&stringArr, startIndex: 0, endIndex: stringArr.count - 1)
    reverseWord(&stringArr)
    return String(stringArr)
}

/// 1. Remove excessive spaces (leading, trailing, and between words)
func removeSpace(_ s: String) -> [Character] {
    let ch = Array(s)
    var left = 0
    var right = ch.count - 1
    // Ignore leading spaces
    while ch[left] == " " {
        left += 1
    }
    // Ignore trailing spaces
    while ch[right] == " " {
        right -= 1
    }

    // Now deal with excessive spaces in between
    var lastArr = Array<Character>()
    while left <= right {
        let char = ch[left]
        if char != " " || lastArr[lastArr.count - 1] != " "  {
            lastArr.append(char)
        }
      
        left += 1
    }
    return lastArr
}

/// 2. Reverse the entire string
func reverseString(_ s: inout [Character], startIndex: Int, endIndex: Int)  {
    var start = startIndex
    var end = endIndex
    while start < end {
        (s[start], s[end]) = (s[end], s[start])
        start += 1
        end -= 1
    }
}

/// 3. Reverse each word in the string
func reverseWord(_ s: inout [Character]) {
    var start = 0
    var end = 0
    var entry = false

    for i in 0..<s.count {
        if !entry {
            start = i
            entry = true
        }
      
        if entry && s[i] == " " && s[i - 1] != " " {
            end = i - 1
            entry = false
            reverseString(&s, startIndex: start, endIndex: end)
        }

        if entry && (i == s.count - 1) && s[i] != " " {
            end = i
            entry = false
            reverseString(&s, startIndex: start, endIndex: end)
        }
    }
}

Scala:

object Solution {
  def reverseWords(s: String): String = {
    var sb = removeSpace(s) // Remove excessive spaces
    reverseString(sb, 0, sb.length - 1) // Reverse string
    reverseEachWord(sb)
    sb.mkString
  }

  // Remove excessive spaces
  def removeSpace(s: String): Array[Char] = {
    var start = 0
    var end = s.length - 1
    // Remove leading spaces
    while (start < s.length && s(start) == ' ') start += 1
    // Remove trailing spaces
    while (end >= 0 && s(end) == ' ') end -= 1
    var sb = "" // String
    // While start is less than or equal to end, proceed with the addition
    while (start <= end) {
      var c = s(start)
      // If the current character is not space or the last character of sb is not space, append to sb
      if (c != ' ' || sb(sb.length - 1) != ' ') {
        sb ++= c.toString
      }
      start += 1 // Move pointer to the right
    }
    sb.toArray
  }

  // Reverse string
  def reverseString(s: Array[Char], start: Int, end: Int): Unit = {
    var (left, right) = (start, end)
    while (left < right) {
      var tmp = s(left)
      s(left) = s(right)
      s(right) = tmp
      left += 1
      right -= 1
    }
  }

  // Reverse each word
  def reverseEachWord(s: Array[Char]): Unit = {
    var i = 0
    while (i < s.length) {
      var j = i + 1
      // Iteratively search for index of each word
      while (j < s.length && s(j) != ' ') j += 1
      reverseString(s, i, j - 1)  // Reverse each word
      i = j + 1   // Move i to the next position
    }
  }
}

PHP:

function reverseWords($s) {
    $this->removeExtraSpaces($s); 
    $this->reverseString($s, 0, strlen($s)-1);
    // Reverse each word
    $start = 0; 
    for ($i = 0; $i <= strlen($s); $i++) {
        // Reached a space or end of string indicates the end of a word. Reverse.
        if ($i == strlen($s) || $s[$i] == ' ') { 
            // Reverse, note that it is a closed interval [] reverse.
            $this->reverseString($s, $start, $i-1);
            // +1: Words are separated by a space
            $start = $i + 1; 
        }
    }
    return $s;
}

// Remove excessive spaces
function removeExtraSpaces(&$s){
    $slow = 0;   
    for ($i = 0; $i < strlen($s); $i++) {
        if ($s[$i] != ' ') { 
            if ($slow != 0){
                $s[$slow++] = ' ';
            } 
            while ($i < strlen($s) && $s[$i] != ' ') { 
                $s[$slow++] = $s[$i++];
            }
        }
    }
    // Move and cover operation, discarding excess dirty data.
    $s = substr($s,0,$slow);
    return ;
}

// Reverse string
function reverseString(&$s, $start, $end) {
    for ($i = $start, $j = $end; $i < $j; $i++, $j--) {
        $tmp = $s[$i];
        $s[$i] = $s[$j];
        $s[$j] = $tmp;
    }
    return ;
}

Rust:

// Implement based on the idea of C++ version two
// Convert function names from camelCase to snake_case based on Rust compiler suggestions
impl Solution {
    pub fn reverse(s: &mut Vec<char>, mut begin: usize, mut end: usize){
        while begin < end {
            let temp = s[begin];
            s[begin] = s[end];
            s[end] = temp;
            begin += 1;
            end -= 1;
        }
}
pub fn remove_extra_spaces(s: &mut Vec<char>) {
        let mut slow: usize = 0;
        let len = s.len();
        // Note that you cannot use a for loop here; otherwise, incrementing i inside the inner while loop will be ineffective
        let mut i: usize = 0;
        while i < len {
            if !s[i].is_ascii_whitespace() {
                if slow != 0 {
                    s[slow] = ' ';
                    slow += 1;
                }
                while i < len && !s[i].is_ascii_whitespace() {
                    s[slow] = s[i];
                    slow += 1;
                    i += 1;
                }
            }
            i += 1;
        }
        s.resize(slow, ' ');
    }
    pub fn reverse_words(s: String) -> String {
        let mut s = s.chars().collect::<Vec<char>>();
        Self::remove_extra_spaces(&mut s);
        let len = s.len();
        Self::reverse(&mut s, 0, len - 1);
        let mut start = 0;
        for i in 0..=len {
            if i == len || s[i].is_ascii_whitespace() {
                Self::reverse(&mut s, start, i - 1);
                start = i + 1;
            }
        }
        s.iter().collect::<String>()
    }
}

C:

// Reverse characters in a specified range of a string
void reverse(char* s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        int tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}

// Remove excessive spaces from both ends and the middle of the string
void removeExtraSpace(char* s) {
    int start = 0; // Pointer to the beginning of the string
    int end = strlen(s) - 1; // Pointer to the end of the string
    while (s[start] == ' ') start++; // Move the start pointer until a non-space character is found
    while (s[end] == ' ') end--; // Move the end pointer until a non-space character is found
    int slow = 0; // Pointer to the next write position of the new string
    for (int i = start; i <= end; i++) { // Traverse the entire string
        if (s[i] == ' ' && s[i+1] == ' ')  { // If the current character is a space and the next character is also a space, skip it
            continue;
        }
        s[slow] = s[i]; // Otherwise, copy the current character to the slow position of the new string
        slow++; // Move the slow pointer backwards
    }
    s[slow] = '\0'; // Add a null character at the end of the new string
}

// Reverse words in a string
char * reverseWords(char * s){
    removeExtraSpace(s); // First remove excessive spaces from both ends and the middle of the string
    reverse(s, 0, strlen(s) - 1); // Reverse the entire string
    int slow = 0; // Pointer to the start position of each word
    for (int i = 0; i <= strlen(s); i++) { // Traverse the entire string
        if (s[i] ==' ' || s[i] == '\0') { // If the current character is a space or null character, it means a word has ended
            reverse(s, slow, i-1); // Reverse the word
            slow = i + 1; // Set the slow pointer to the start position of the next word
        }
    }
    return s; // Return the processed string
}

C#

public string ReverseWords(string s) {
    return string.Join(' ', s.Trim().Split(' ',StringSplitOptions.RemoveEmptyEntries).Reverse());
}