NUHMAN.com

Introduction

LeetCode 151 asks us to reverse the words in a given string. The input is a string containing words separated by spaces. We are required to reverse the words while maintaining their original order and removing extra spaces.

The challenge is to reverse the words in-place, without using extra space for another string (except for a minimal amount of space for internal operations).

Problem Statement

You are given a string s, where each word is separated by a space. You need to reverse the words in the string without changing the order of the words themselves. Leading and trailing spaces in the string must be removed, and there should only be a single space between words in the resulting string.

Function Signature:

go

func reverseWords(s string) string

Approach

Key Idea:

We can approach this problem in a few key steps:

1. Trim Leading and Trailing Spaces: First, remove any extra spaces at the start and end of the string.
2. Split Words: Split the string into individual words using space as the delimiter.
3. Reverse Words Order: Reverse the order of words in the list.
4. Join the Words: Finally, join the words back into a single string with exactly one space separating them.

We aim to solve this problem efficiently in O(n) time complexity, where n is the length of the string.

Go Implementation

go

package main

import (
	"fmt"
	"strings"
)

func reverseWords(s string) string {
	// Step 1: Trim any leading or trailing spaces
	s = strings.TrimSpace(s)

	// Step 2: Split the string into words based on spaces
	words := strings.Fields(s)

	// Step 3: Reverse the words in the list
	for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
		words[i], words[j] = words[j], words[i]
	}

	// Step 4: Join the words with a single space and return the result
	return strings.Join(words, " ")
}

func main() {
	// Example usage
	s := "  the sky is blue  "
	result := reverseWords(s)
	fmt.Println("Reversed Words:", result) // Output: "blue is sky the"
}

Explanation of the Code:

1. Trim the String:

• We use strings.TrimSpace(s) to remove any leading or trailing spaces from the input string.

1. Split the String into Words:

• strings.Fields(s) splits the string into words. It handles multiple spaces between words by ignoring extra spaces and splitting based only on non-empty words.

1. Reverse the Words:

• We reverse the words in place by using two pointers (i and j). i starts from the beginning, and j starts from the end. We swap the words at positions i and j, then increment i and decrement j until i meets j.

1. Join Words into a Single String:

• Finally, we use strings.Join(words, " ") to join the reversed words back into a single string with a space between each word.

Time and Space Complexity

OperationComplexityTimeO(n)SpaceO(n)

• Time Complexity:
• TrimSpace takes O(n) time to remove leading and trailing spaces.
• Fields splits the string into words in O(n) time.
• Reversing the words takes O(k) time, where k is the number of words, which is at most O(n) because the number of words is at most the length of the string.
• Joining the words back together takes O(n) time.
• Overall time complexity is O(n), where n is the length of the input string.
• Space Complexity:
• The space complexity is O(n) because we store the split words and the resulting string in memory.

Example

Input:

go

s := "  the sky is blue  "

Output:

arduino

"blue is sky the"

Explanation:

1. Trim: " the sky is blue " becomes "the sky is blue".
2. Split: ["the", "sky", "is", "blue"].
3. Reverse: ["blue", "is", "sky", "the"].
4. Join: "blue is sky the".

Why This Approach Works

• Efficiency: The approach is efficient because it processes the string in linear time, using a few built-in Go functions that handle edge cases (like extra spaces) internally.
• In-place Reversal: The solution reverses the words using a two-pointer technique, avoiding the need for additional space for a reversed list, other than the space needed for the input/output.
• No Extra Space Between Words: By using strings.Fields and strings.Join, we ensure that words are separated by exactly one space in the final output, removing any extra spaces between words.

Conclusion

This solution demonstrates how to efficiently reverse the words in a string with minimal space and time complexity. By utilizing built-in string functions, we avoid manually handling spaces or performing multiple passes over the string.