問題
文字列 s をs は、
- 単語は、
空白を 含まない 1 文字以上の ひとまとまりです - 先頭と
末尾の 空白は 捨てます。 単語の 間に 空白が 2 つ以上続いていても、 返す文字列では 1 つにします - 単語が 1 つも
無い ときは、 空の 文字列を返します sの長さは 0 以上 10000 以下で、 英字、 数字、 半角の 空白だけで できています
入力と出力の例
例 1
入力
s = "cats like warm milk"出力
"milk warm like cats"例 2
先頭と
入力
s = " open the door "出力
"door the open"例 3
単語が 1 つだけなら、
入力
s = "hello"出力
"hello"面接での聞かれ方
面接では、
- 「文の
単語の 順番を 逆に してください」 - 書き終えた
あとに 「split を 使わずに 書けますか？」と 続けて 聞かれます - 「空白が続いていたら？」
「空の文字列なら？」と、 端の 場合を 聞かれる こともあります
単語の
まず
段 1
まずはs.split() でreversed で" ".join でsplit() は、
段 2
面接では
段 3
始まりのi から、j をi から j のi を j に
ここから解答です。先に自分で書いてから読むと、考え方が残ります。
解答
Python
Python
def reverse_words(s):
words = []
i = 0
n = len(s)
while i < n:
if s[i] == " ":
i += 1
continue
j = i
while j < n:
if s[j] == " ":
break
j += 1
words.append(s[i:j])
i = j
words.reverse()
return " ".join(words)JavaScript
JavaScript
function reverseWords(s) {
const words = [];
const n = s.length;
let i = 0;
while (i < n) {
if (s[i] === " ") {
i++;
continue;
}
let j = i;
while (j < n) {
if (s[j] === " ") {
break;
}
j++;
}
words.push(s.slice(i, j));
i = j;
}
words.reverse();
return words.join(" ");
}段 2 と" ".join(reversed(s.split())) の 1 行で
計算量
- 時間は O(n) です。
iとjはどちらも 前に しか進まないので、 文字は 合わせて 一定の 回数しか 読みません - 使う
記憶は O(n) です。 切り出した 単語を 並びに 覚え、 つないだ文字列も 新しく作ります - 段 1 の split を
使う 書き方も、 時間と 記憶は どちらも O(n) です
よく
- JavaScript で
s.split(" ")を使う。 空白 1 つで区切ると、 続いた 空白や 先頭の 空白の ところに 空の 文字列が 入ります。 例 2 で "door the open"のように、空白が 多いまま 返ってしまいます - 単語の
中の 文字まで 逆にする。 文字列を まる ごと 逆に すると "klim mraw ekil stac"になります。 逆に するのは 単語の 順だけです - 内側の
繰り返しで 終わりを 確かめ忘れる。 j < nを先に 書かないと、 最後の 単語で 文字列の 外を 読みにいきます
面接での
書き始める
「空白で
単語に 分けて、 並びを 逆に して、 空白 1 つで つなぎます。 split を 使えば 1 行ですが、 使わない 書き方も できます。 前から 読んで、 空白は 飛ばし、 空白でない 文字から 次の 空白までを 1 つの 単語として 切り出します。 時間も 記憶も O(n) です。」
書き終えたら、
「例 2 の
" open the door "でたどります。 先頭の 空白 2 つは 飛ばし、 open を 切り出します。 続く 空白 3 つも 飛ばすので、 空の 単語は 入りません。 最後に open、 the、 door の 並びを 逆に して、 door the open を 返します。」