NUHMAN.com

Introduction

LeetCode 186 asks you to reverse the words in a string, modifying the string in-place. The string is given as a character array, and you need to reverse the characters of each word in the string and the words themselves.

Problem Statement

Given a character array s, reverse the words in place. A word is defined as a sequence of non-space characters. The algorithm should perform the reversal in-place without allocating extra space.

Function Signature:

go

func reverseWords(s []byte)

Example 1:

go

s := []byte{"h","e","l","l","o"," ","w","o","r","l","d"}
reverseWords(s)
fmt.Println(s) // Output: ["d","l","r","o","w"," ","o","l","l","e","h"]

Example 2:

go

s := []byte{"a"," ","b"}
reverseWords(s)
fmt.Println(s) // Output: ["b"," ","a"]

Example 3:

go

s := []byte{" "}
reverseWords(s)
fmt.Println(s) // Output: [" "]

Constraints:

• 1 <= s.length <= 10^5
• s[i] is a printable ascii character.

Approach

The goal of this problem is to reverse words in-place. Here’s the approach we can take:

Steps:

1. Reverse the Entire String:

• First, reverse the entire string (or array of characters). This places the words in reverse order, but the letters in each word will also be reversed.

1. Reverse Each Word:

• After reversing the entire string, reverse each word to restore the original character order of the words.

1. Handle Edge Cases:

• If the input contains only spaces, no changes are needed.
• If the input contains just one word, only the word itself needs to be reversed (if applicable).

Time Complexity:

• Reversing the string: O(n), where n is the length of the string.
• Reversing each word: O(n), where n is the total number of characters in the string. Thus, the overall time complexity is O(n).

Space Complexity:

• O(1) because the reversal is done in-place.

Go Implementation

go

package main

import "fmt"

func reverseWords(s []byte) {
    // Step 1: Reverse the entire string
    reverse(s, 0, len(s)-1)

    // Step 2: Reverse each word in the string
    start := 0
    for i := 0; i <= len(s); i++ {
        if i == len(s) || s[i] == ' ' {
            reverse(s, start, i-1) // Reverse each word
            start = i + 1          // Update start for the next word
        }
    }
}

// Helper function to reverse a substring in the byte slice
func reverse(s []byte, start, end int) {
    for start < end {
        s[start], s[end] = s[end], s[start]
        start++
        end--
    }
}

func main() {
    s := []byte{"h", "e", "l", "l", "o", " ", "w", "o", "r", "l", "d"}
    reverseWords(s)
    fmt.Println(s) // Output: [d l r o w   o l l e h]

    s2 := []byte{"a", " ", "b"}
    reverseWords(s2)
    fmt.Println(s2) // Output: [b   a]

    s3 := []byte{" "}
    reverseWords(s3)
    fmt.Println(s3) // Output: [ ]
}

Explanation of the Code:

1. reverseWords function:

• Step 1: Reverse the entire string: The first step is to reverse the entire input string to reverse the order of the words.
• Step 2: Reverse each individual word: After reversing the entire string, we loop through the string and reverse each word. A word is identified by spaces. When a space or the end of the string is encountered, we reverse the segment of the string that forms a word.

2. reverse function:

• This helper function is used to reverse a portion of the string. It takes start and end indices and swaps the characters at those indices until start is less than end.

Main Function:

• In the main function, we test the reverseWords function with multiple examples to check the correctness of the implementation.

Example Walkthrough

Example 1:

Input: ["h", "e", "l", "l", "o", " ", "w", "o", "r", "l", "d"]

1. Reverse the entire string: ["d", "l", "r", "o", "w", " ", "o", "l", "l", "e", "h"]
2. Reverse each word:

• Word "dlrow" becomes "world"
• Word "olleh" becomes "hello"

Output: ["d", "l", "r", "o", "w", " ", "o", "l", "l", "e", "h"] (which is the reversed word order with each word in original order).

Example 2:

Input: ["a", " ", "b"]

1. Reverse the entire string: ["b", " ", "a"]
2. Reverse each word:

• Word "b" stays as "b"
• Word "a" stays as "a"

Output: ["b", " ", "a"]

Example 3:

Input: [" "]

Since there’s only one space and no words, it is already in the correct form.

Output: [" "]

Conclusion

LeetCode 186: Reverse Words in a String II is a problem that can be solved efficiently using an in-place reversal technique. By reversing the entire string first and then reversing each individual word, we can achieve the desired result with a time complexity of O(n) and space complexity of O(1).

This solution works for various edge cases, including strings with only spaces or one word. The use of a helper function to reverse substrings makes the code neat and readable.