題目

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.

Example 1

1
2
Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2

1
2
3
Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3

1
2
3
Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

  • 1 <= s.length <= 104
  • s contains English letters (upper-case and lower-case), digits, and spaces ‘ ‘.
  • There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?
( 等 leetcode 186 再做 )

解釋題目

給你一個字串 s，請你將字串中的「單詞」順序反轉，並回傳一個新的字串。

  • 「單詞」定義為一串非空白字元的連續序列。
  • 單詞之間至少會有一個空格分隔。
  • s 可能包含前導空格、尾隨空格，或是單詞之間有多個空格。
  • 回傳的字串中，單詞之間只用一個空格分隔，且不能有多餘的空格（前後都不能有）。

思路(1)

  1. 不用 split() 的話，就是從字串尾端遍歷回來，一開始的 index 會是最後一個字母
  2. 需要用兩個 while 迴圈，一開始遇到空字串要跳過 (continue)
  3. 遇到第一個單詞時，紀錄單詞最後一個字母的 index，也就是 end = n
  4. 第二個 while 迴圈，找出單詞的第一個字母，while 停止條件
    • 當遇到 s[n] == " " 時
    • 還有 n >= 0，此情況是遍歷到整個字串第一個字母時。
  5. 取到的單詞會是 s[start: end + 1]
  6. 把單詞 append 起來候用空格 " " join 起來。

程式碼(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
class Solution:
    def reverseWords(self, s: str) -> str:
        n = len(s) - 1
        reverse_str = []

        while n >= 0:
            if s[n] == " ":
                n = n - 1
                continue

            end = n
            while n >=0 and s[n] != " ": 
                start = n 
                n = n - 1
                
            reverse_str.append(s[start:end + 1])

        return " ".join(reverse_str)

思路(2)

  1. 只是要解出來，用 python split() 函式可以去掉多餘空格
  2. 再倒著遍歷，最後用空格 join 回來

程式碼(2)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split()
        res = []

        for i in range(len(words) - 1, -1, -1):
            res.append(words[i])
            if i != 0:
                res.append(" ")

        return "".join(res)