- Reverse Words in a String
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
func reverseWords(s string) string {
// Convert string to byte slice for in-place modifications
ss := []byte(s)
n := len(s)
slow, fast := 0, 0
// Step 1: Remove leading spaces
for fast < n && ss[fast] == ' ' {
fast++
}
// Slice the byte slice to remove leading spaces
ss = ss[fast:]
n = len(ss)
// Reset pointers for next steps
slow, fast = 0, 0
// Step 2: Remove extra spaces between words
for fast < n {
if fast > 0 && ss[fast-1] == ' ' && ss[fast] == ' ' {
fast++
continue
}
ss[slow] = ss[fast]
slow++
fast++
}
// Step 3: Remove trailing space
if slow > 0 && ss[slow-1] == ' ' {
ss = ss[:slow-1]
} else {
ss = ss[:slow]
}
// Step 4: Reverse the entire byte slice
reverse(&ss, 0, len(ss)-1)
// Step 5: Reverse each word within the byte slice
i := 0
for i < len(ss) {
j := i
for j < len(ss) && ss[j] != ' ' {
j++
}
reverse(&ss, i, j-1)
i = j + 1
}
// Convert byte slice back to string and return
return string(ss)
}
// Helper function to reverse a portion of the byte slice
func reverse(b *[]byte, left, right int) {
for left < right {
(*b)[left], (*b)[right] = (*b)[right], (*b)[left]
left++
right--
}
}
Here are the steps:
- removing prefix spaces: This loop moves the fast pointer forward, skipping any leading spaces at the beginning of the byte slice.
- removing spaces in between:
- It skips consecutive spaces by checking if the current and previous characters are both spaces.
- It copies valid characters to the slow pointer, effectively removing extra spaces.
- It compacts the byte slice in place, building the cleaned version without extra spaces.
- removing trailing spaces, same logic as removing prefix
- reverse entire string
- reverse each word
- return string
In fact, the time complexity above is O(n), and we can actually use the built-in go functions to achieve above. I have this just for fun.
func reverseWords(s string) string {
// Step 1: Trim leading and trailing spaces
s = strings.TrimSpace(s)
// Step 2: Split the string into words
words := strings.Fields(s)
// Step 3: Reverse the order of words
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 back into a single string with a single space separating each word
return strings.Join(words, " ")
}