151. Reverse Words in a String

題目連結

思路

本題可以算是 344. Reverse String 的延伸，不過在這之上增加了比較複雜的要求，即是翻轉單字的順序而不將單字本身的字母整個反轉，例如 hello world 在一般的反轉字串題目中要變成 dlrow olleh，而本題所要求的輸出會是 world hello，並且還會出現多餘的空白這樣的狀況，在翻轉的過程中也需要確保多餘的空白被清除。因此本題我們會需要先準備兩個函式以方便後續的處理，分別是 reverse 用來反轉輸出的字串以及 removeExtraSpace 來去除多餘的空白。

首先是 reverse，實際上這個函式也是能夠解開 344. Reverse String 的方法，要實作出這個方法並不困難，也有部分語言有提供內建的方法可以直接調用，不過如果想要手刻出同樣的效果並能維持 inplace 反轉的話，會需要利用到雙指標的概念。具體上我們可以從字串的開頭和結尾同時出發，每次進行互換之後就將左右兩邊的指標向中間推，直到兩個指標碰在一起的時候就完成反轉，可以參考下面的函式：

func reverse(s []byte) {
  left := 0
  right := len(s) - 1

  for left < right {
    s[left], s[right] = s[right], s[left]
    left++
    right--
  }
}

接下來是 removeExtraSpace，概念上是透過一個慢指標來控制單字位置的重新調整，再一次性的把後半段多餘的地方切掉。具體的作法可以參考下面的示意：

可以注意到 slow 只有在遇到非空白的字元時才會被移動，它的使命是在單字之間添加一個空白之後 (開頭例外) 把 i 所在位置的單字給搬到 slow 的地方來達到去除多餘空白的效果，並且當迴圈結束之後 slow 的位置也恰好是我們所要的去除空白後的完整字串的結尾位置。因此這個函式可以寫成這樣：

func removeExtraSpace(s []byte) []byte {
  slow := 0 

  for i := 0;i < len(s); i++ {
    if s[i] != ' ' { // 遇到單字的開頭
      if slow != 0 { // 代表是第一個之後的單字
        s[slow] = ' ' // 需要在單字之間加上一個空白
        slow++
      }
      
      for i < len(s) && s[i] != ' ' { // 把目前遇到的單字搬到 slow 的位置
        s[slow] = s[i]
        slow++
        i++
      } 
    }
  }

  return s[0:slow]
}

最後終於可以來處理本題的邏輯了，由於本題的輸入會出現多餘的空白，因此在一開始我們會先使用剛剛設計的 removeExtraSpace 來清理字串，接下來反轉的邏輯會是「先將字串整個完全反轉，再將每個單字反轉一次」即完成題目的要求，也就是先經過一次 reverse 完全反轉字串後，接下來加入一個慢指標 slow 然後開始跑一個 for 迴圈，當遇到一個新的單字的時候把當下的位置記錄在 slow，然後將 i 繼續往後推直到遇到空白，此時 slow 到 i 之間就是一個完整的單字了，接下來只要把這一段再進行一次 reverse 就可以還原成原本單字的順序，以此類推跑完整個迴圈後就完成了。

Full Code

Golang

func removeExtraSpace(s []byte) []byte {
    slow := 0
  
    for i := 0; i < len(s); i++ {
        if s[i] != ' ' {
            if slow != 0 {
                s[slow] = ' '
                slow++
            }
          
            for i < len(s) && s[i] != ' ' {
                s[slow] = s[i]
                slow++
                i++
            }
        }
    }

    return s[0:slow]
}

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

func reverseWords(s string) string {
    ss := []byte(s)
    sss := removeExtraSpace(ss)

    reverse(sss) 

    slow := 0
    for i := 0; i < len(sss); i++ {
        if sss[i] != ' ' {
            slow = i // 一個單字的開頭
            for i < len(sss) && sss[i] != ' ' { // 找到單字的結尾
                i++
            }
            reverse(sss[slow:i]) // 再反轉一次還原單字
        }
    }

    return string(sss)
}