Reverse Words in a String
単語とスペースで構成された文字列 s が与えられます。単語とは、内部にスペースを含まない、英字と数字の連続です。単語は複数のスペースで区切られている場合があり、s の先頭や末尾にスペースが含まれている場合もあります。
単語を逆順にし、単語間をちょうど1つのスペースでつないで返してください。先頭にも末尾にもスペースを含めません。各単語の綴りはそのままで、変わるのは単語の順序だけです。
関数
- sstring
- 少なくとも1つの単語を含む文字、数字、スペース
- 戻り値string
- s の単語を逆順に並べ、単一のスペースで区切ったもの
制約
1 ≤ s.length ≤ 104sには英字、数字、スペースのみが含まれます。sには少なくとも1つの単語が含まれています。
例
- 入力
- s = "Coddy runs in 15 languages"
- 出力
- "languages 15 in runs Coddy"
- 説明
- 単語は
Coddy、runs、in、15、languagesです。最後から最初へ読むとlanguages 15 in runs Coddyになります。単語には数字が含まれることがあるため、15も単語として数えられます。
- 入力
- s = " practice makes progress "
- 出力
- "progress makes practice"
- 説明
- 両端のスペースは削除され、単語間の2つおよび3つの連続したスペースは1つに縮まります。3つの単語は最後から最初の順に出力されます:
progress makes practice。
- 入力
- s = " single "
- 出力
- "single"
- 説明
- 1語のリストは、逆から読んでも同じです。前後の空白だけがなくなるので、答えは
singleです。
発展問題
単語を逆順にしつつ、s の空白はそのまま保てますか？つまり、同じ長さの空白の連続を、同じ順序で保てますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
- 少しの間、空白のことは忘れましょう。単語がすでにリストに入っていたら、どうやって答えを組み立てますか？次に、余分な空白が文字列を単語に分割する処理にどのような影響を与えるか考えてみましょう。
スペースで分割し、連続する2つのスペースや先頭または末尾のスペースによって残される空の要素を取り除きます。単語のリストを逆順にして、単一のスペースで結合します。
1つの文字配列内で処理するには、代わりに配列全体を反転します。これにより単語の順序は正しくなりますが、それぞれの単語は逆向きにつづられます。次に、各単語を元に戻します。2つ目のインデックスを使って文字を前向きにコピーすれば、連続する空白がすべて1つに縮まります。
解説
単語の順序は1回の反転です。解答が失敗する原因となるのは空白です。両端の空白と単語間の連続した空白は取り除き、答えでは単語間を空白1つだけにする必要があります。単語をリストに分割する方法も、文字列全体を反転してから、1つの配列内の各単語を反転する方法もあります。
単語に分割して逆順に結合する
考え方
sを単語に分割し、リストを逆順にして、単一のスペースで結合します。分割には注意が必要です。" practice makes progress "を各スペースで分割すると、3つの単語の前後に6つの空の要素ができます。空の要素を取り除くと、リストはpractice、makes、progressになります。
分割では各文字を1回読み取り、結合では残した各文字を1回書き込むため、長さnの文字列に対する時間計算量はO(n)です。単語のリストと答えには、追加でO(n)の領域が必要です。
アルゴリズム
sをスペースで分割します。- 空の要素を取り除きます。
- 単語のリストを逆順にします。
- 単語をそれぞれ1つのスペースでつなぎ、その結果を返します。
def reverseWords(s):
# split() with no argument treats any run of spaces as one separator
# and ignores spaces at both ends.
words = s.split()
words.reverse()
return " ".join(words)文字列全体を反転し、次に各単語を反転する
考え方
文字列全体を逆順にすると単語の順序は正しくなりますが、それぞれの単語が逆さにつづられます。Coddy runs in 15 languagesはsegaugnal 51 ni snur yddoCになります。各単語を個別に逆順にすると、languages 15 in runs Coddyになります。
空白も同じパスで処理します。readインデックスは逆順にした配列を走査して空白を飛ばし、writeインデックスは次に残す文字を書き込む位置を示します。writeがreadを追い越すことはないため、コピーによってまだ必要な文字が上書きされることはありません。単語の前に書き込まれる1つの空白は、readが飛ばした少なくとも1つの空白の代わりになります。
各文字は最大1回コピーされ、最大2回入れ替えられるため、時間計算量はO(n)です。編集可能な文字バッファを使う場合、追加の空間計算量はO(1)です。ここでは文字列は値として渡されるため、各解法ではsの作業用コピーを1つ作成し、合計メモリ使用量はO(n)になります。
アルゴリズム
sを文字配列にコピーし、配列全体を逆順にします。- 読み取りインデックスで配列をたどり、空白をスキップします。
- 各単語の先頭で、最初の単語でない場合はまず空白を1つ書き込み、その後、単語の文字を書き込みインデックスにコピーします。
- コピーした範囲を逆順にして、単語が前から読めるようにします。
- 先頭から
write文字を返します。
def reverseWords(s):
chars = list(s)
def reverse(lo, hi):
while lo < hi:
chars[lo], chars[hi] = chars[hi], chars[lo]
lo += 1
hi -= 1
n = len(chars)
reverse(0, n - 1) # words in the right order, each spelled backwards
write = 0
read = 0
while read < n:
if chars[read] == " ":
read += 1
continue
if write > 0:
chars[write] = " " # one space before every word but the first
write += 1
start = write
while read < n and chars[read] != " ":
chars[write] = chars[read]
write += 1
read += 1
reverse(start, write - 1) # spell the word forwards again
return "".join(chars[:write])
落とし穴と境界ケース
- 半角スペース1つで分割し、すべての要素を残すこと。
"a b"を分割すると、a、空の要素、bになり、結合すると2つのスペースが戻って"b a"になります。 - 分割時に先頭や末尾の空要素が削除されると思い込むこと。Javaの
split(" ")は末尾の空要素を削除しますが、先頭の空要素は残すため、" a b"では空要素が1つ残ります。 - 最後の単語も含め、すべての単語の後ろにスペースを追加すること。そうすると答えの末尾にスペースが残ります。最初の単語以外の各単語の前にスペースを置きましょう。
- その場で反転する方法で、反転を1回しかしないこと。単語だけを反転すると、
yddoC snur ni 51 segaugnalになります。 - PHPとRでは、
2026のような数字だけの入力が数値として渡される場合があります。分割する前に文字列に変換しましょう。
よくある質問3
文字列内の単語を反転する処理の時間計算量はどれくらいですか？
どちらの方法も、長さが n の文字列に対して O(n) 時間で実行されます。各文字を読み書きする回数が定数回だからです。分割では単語のリスト用に O(n) の追加領域を使います。文字列全体を反転してから各単語を反転する方法では、編集可能な文字配列上で O(1) の追加領域が必要です。
単語間に複数のスペースがある場合、どのように処理しますか？
単語はスペース以外の文字が連続したものとして扱い、入力のスペースは決してコピーしないでください。Python と Ruby では区切り文字を指定せずに分割し、Go では strings.Fields、Rust では split_whitespace を使うと、スペースの連続と両端のスペースがすべて自動的に除去されます。それ以外の場合は、空の要素を取り除いてください。その後、単語の間にスペースを1つ入れてください。
split関数を使わずに単語を逆順にできますか？
はい。右端から走査し、空白を飛ばして単語の終わりの位置を記録し、左に移動して単語の先頭まで進みます。そして、最初の単語でない限り、その単語の前に空白を付けて追加します。各文字を一度ずつ調べるため、時間計算量はO(n)のままで、反転させるリストを使わずに単語が逆順になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def reverseWords(s):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "Coddy runs in 15 languages"
期待される出力
"languages 15 in runs Coddy"