Leetcode 151 Reverse Words in a String
  1. 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:

  1. removing prefix spaces: This loop moves the fast pointer forward, skipping any leading spaces at the beginning of the byte slice.
  2. 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.
  1. removing trailing spaces, same logic as removing prefix
  2. reverse entire string
  3. reverse each word
  4. 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, " ")
}