【LeetCode】 151. Reverse Words in a String 解答・解説【Python】

はじめに
1. ポイント
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python
  2. 解答2：Python, Brute Force, 英語コメント
終わりに
1. 補足・参考・感想
2. 疑問が解決した方は他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- 文字列とリスト(配列)の扱い
- 文字列とリストの変換

詳細

問題

原文

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:

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

1
2

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

Example 2:

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

1
2
3

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

Example 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.

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 <= 10⁴

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?

内容(和訳)

与えられた入力文字列sを単語の順序を逆にします。

単語はスペース以外の文字のシーケンスと定義されます。s内の単語は少なくとも1つのスペースで区切られます。

単語を逆の順序で、単一のスペースで連結した文字列を返します。

sには前後のスペースや単語間の複数のスペースが含まれる可能性があることに注意してください。返される文字列には単語を区切るための単一のスペースのみが含まれるようにします。余分なスペースは含めません。

※cahtGPTによる翻訳

解答

解答1：Python

class Solution:
    def reverseWords(self, s: str) -> str:
        #戻り値用のリストを用意
        reversed_words = []
        #1単語を保持する変数
        word = ""
        #sを一巡する
        for i in range(len(s)):
            #wordに文字があり、i番目の文字が空白の場合
            if word and s[i]==" ":
                #戻り値用のリストにwordを追加
                reversed_words.append(word)
                #wordを空文字に戻して次の単語を保持する準備をする
                word = ""
            #i番目の文字が空白以外の場合
            elif s[i]!=" ":
                #wordにその文字を追加　→blu + e　→blue
                word += s[i]
        #走査終了後、wordに文字があれば、戻り値用のリストに追加
        if word: reversed_words.append(word)
        #リストを逆順にして空白区切りの文字列で返す
        return " ".join(reversed_words[::-1])

class Solution:

def reverseWords(self, s: str) -> str:

#戻り値用のリストを用意

reversed_words = []

#1単語を保持する変数

word = ""

#sを一巡する

for i in range(len(s)):

#wordに文字があり、i番目の文字が空白の場合

if word and s[i]==" ":

#戻り値用のリストにwordを追加

reversed_words.append(word)

#wordを空文字に戻して次の単語を保持する準備をする

word = ""

#i番目の文字が空白以外の場合

elif s[i]!=" ":

#wordにその文字を追加　→blu + e　→blue

word += s[i]

#走査終了後、wordに文字があれば、戻り値用のリストに追加

if word: reversed_words.append(word)

#リストを逆順にして空白区切りの文字列で返す

return " ".join(reversed_words[::-1])

解答2：Python, Brute Force, 英語コメント

"""
■問題の内容を確認
Let me check my understand about your question.
I'm given an input string "s".
s has words which each word is splited by single space.
 ※correction:Each word is splited by at least one space.
I have to return words as single string which each word is splited by single space.

■問題の前提を確認:Assumption
Let's talk about some assumption.


■テストケース
・一般的な内容
"hello world"


・エッジケース
" hello world "
" "

■解法と計算量
1.Brute Force
Performe two for loop.
In first for loop, I split each word in array splited by a single space.
In second for loop, iterate from the end of array to start.
And check if each element of array is not space.
If the condition is true, the element is added to the variable for return.
And single space is also added to the variable.

After seconde for loop, return the variable except for last letter
because last element is space.
"""

class Solution:
    def reverseWords(self, s: str) -> str:
        #Use split method instead of first loop.
        word_list = s.split(" ")
        answer = ""
        for i in word_list[::-1]:
            if i!= "":
                answer += i
                answer += " "
        return answer[:-1]

"""

■問題の内容を確認

Let me check my understand about your question.

I'm given an input string "s".

s has words which each word is splited by single space.

※correction:Each word is splited by at least one space.

I have to return words as single string which each word is splited by single space.

■問題の前提を確認:Assumption

Let's talk about some assumption.

■テストケース

・一般的な内容

"hello world"

・エッジケース

" hello world "

" "

■解法と計算量

1.Brute Force

Performe two for loop.

In first for loop, I split each word in array splited by a single space.

In second for loop, iterate from the end of array to start.

And check if each element of array is not space.

If the condition is true, the element is added to the variable for return.

And single space is also added to the variable.

After seconde for loop, return the variable except for last letter

because last element is space.

"""

class Solution:

def reverseWords(self, s: str) -> str:

#Use split method instead of first loop.

word_list = s.split(" ")

answer = ""

for i in word_list[::-1]:

if i!= "":

answer += i

answer += " "

return answer[:-1]

解答1と比べて処理時間は速かった。その代わりメモリをより多く消費した

組み込み関数のsplitの実装による影響かもしれない。

splitの実装がどのようになっているか調べてみた方が良いかも。

解答1との比較の際に、トレードオフのポイントとして説明できる部分になる気がする。

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

疑問が解決した方は他の問題もどうぞ

前：1431. Kids With the Greatest Number of Candies

次：392. Is Subsequence

LeetCode 解答・解説記事一覧