Decode String
エンコードされた文字列では、繰り返されるテキストをk[text]のように表します。これはtextをk回連続して書いたものを表します。グループは別のグループの中に置けるため、2[a3[b]]はabbbabbbを表します。エンコードされた文字列sを受け取り、デコードされた文字列を返す関数を書いてください。
どの括弧の外側にもある文字はそのままにします。各カウントは正の整数で、[の直前に書かれ、数字はそれ以外の場所には現れません。
関数
- sstring
- エンコードされた文字列
- 戻り値string
- デコードされた文字列
制約
1 ≤ s.length ≤ 104sには小文字の英字、数字、[、]のみが含まれます。sは有効なエンコーディングです。各[の前には個数があり、対応する]があり、空の角括弧はありません。- すべての個数
kは1 ≤ k ≤ 300を満たし、先頭にゼロはありません。 - 括弧のネストは最大100レベルまでです。
- デコードされた文字列は最大で
5 × 104文字です。
例
- 入力
- s = "2[ab]3[c]x"
- 出力
- "ababcccx"
- 説明
2[ab]はababになり、3[c]はcccになります。xはどの角括弧の外側にもあるため、そのままコピーされ、結果はababcccxになります。
- 入力
- s = "2[x3[yz]]"
- 出力
- "xyzyzyzxyzyzyz"
- 説明
- まず内側をデコードします。
3[yz]はyzyzyzなので、外側のグループの本体はxyzyzyzです。これを2回書くと、xyzyzyzxyzyzyzになります。
- 入力
- s = "q10[w]e"
- 出力
- "qwwwwwwwwwwe"
- 説明
- 個数は 2 桁から読み取られる
10なので、qとeの間にwが 10 回現れます。[の隣にある数字だけを読み取るコードでは、0 回繰り返されます。
提出時に隠しテスト+22件
発展問題
デコードされた文字列は、入力よりはるかに長くなることがあります。デコード後の長さが10^18に達する可能性がある場合、文字列全体を構築せずに、デコードされた文字列の位置iにある文字だけを返すにはどうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
角括弧の中身がわかるまでは
3[...]を書き出すことはできません。また、中にはさらにグループが含まれていることもあります。どの種類のグループなら、いつでもすぐに復号できますか？中にグループを含まないグループは一度に展開できるので、内側から外側へ処理します。
]が現れたら、それが閉じるグループは完成です。そのとき、対応する[の前に待機していたテキストと回数が必要になります。これまでに作ったテキストと読み取り中の数を保持しながら、一度スキャンします。
[が現れたら、その両方をスタックにプッシュして、新しく開始します。]が現れたら、それらをポップし、現在のテキストを繰り返したものを、ポップしたテキストに追加します。10や300も扱えるように、カウントは桁ごとに組み立てます。
解説
個数は括弧の前にありますが、中身が何か分かるまではコピーを書き出せません。また、中にはさらにグループが含まれていることがあります。そのため、グループを展開できるのは、その中にあるすべてのグループが処理し終わってからです。以下の各方法は、最も内側のグループから先に処理する方法です。文字列を内側から外側へ書き換える、再帰呼び出しで内側のグループを処理してから外側のグループを処理する、または未処理の外側のグループをスタックに保持する、のいずれかです。以下では、n は入力の長さ、m はデコード後の文字列の長さ、d は最も深いネストの深さです。
最も内側のグループを展開してから、繰り返します
考え方
紙の上で行うのと同じように文字列をデコードしましょう。中にほかのグループがないグループを見つけ、そのコピーをその場所に書き出して、もう一度確認します。2[x3[yz]]では、グループ3[yz]の中には何もないので、文字列は2[xyzyzyz]になり、さらにもう一度展開すると答えが得られます。
文字列内の最初の]は、必ずそのようなグループを閉じます。それより前に閉じているグループはないので、その文字と対応する[の間に角括弧が入ることはありません。その[は左側にある最も近いもので、カウントはその直前に続く数字です。カウント、角括弧、本文を、本文をk回書いたものに置き換え、]がなくなるまで繰り返します。
これは正しい方法ですが、展開のたびに文字列全体を作り直します。b個のグループがあり、文字列がm文字に近づくまで大きくなると、文字のコピー回数は最大でb × m回になります。グループが約1,300個並んだ隠しテストでは、27,688文字を生成するために約2,500万回のコピーが必要です。一方、入力を1回走査すれば済みます。
アルゴリズム
- 文字列内で最初の
]を見つけます。存在しない場合、文字列はデコード済みです。そのまま返します。 - そこから左に進み、最も近い
[を探します。その間のテキストがグループの本体です。 - さらに左に進み、その
[の前にある数字を読み取り、個数kとします。 - 最初の数字から
]までのすべてを、本体をk回繰り返したもので置き換えます。 - 手順1に戻ります。
def decodeString(s):
# Expand one innermost group at a time until no bracket is left.
while True:
close = s.find("]")
if close == -1:
return s
# The first ']' closes a group with no group inside it,
# and the nearest '[' to its left opens that group.
open_ = s.rfind("[", 0, close)
start = open_
while start > 0 and s[start - 1].isdigit():
start -= 1
times = int(s[start:open_])
s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]再帰下降構文解析
考え方
この形式は再帰的です。エンコードされた文字列は文字とグループの並びであり、グループの本体もまたエンコードされた文字列です。そこで、共有位置から読み取り、現在の階層を終わらせる ] に達するか入力の終端に達するまで読み進め、読み取った内容をデコードして返す関数 decode を1つ書きます。
decode が数字に出会うと、数値全体を読み取り、[ を読み飛ばして、本体をデコードするために自身を呼び出します。その呼び出しは対応する ] で停止します。より深い階層の ] は、すでにより深い呼び出しが読み取っているためです。呼び出し元は ] を読み飛ばし、本体を k 回追加して、読み取りを続けます。2[x3[yz]] の場合、外側の呼び出しは2を読み取ります。次の呼び出しは x と3を読み取り、3つ目の呼び出しは yz を返します。中間の呼び出しは xyzyzyz を返し、外側の呼び出しはそれを2回書き込みます。
入力の各文字は1回ずつ読み取られます。実際のコストはコピーです。出力文字は、それを囲む各グループにつき1回コピーされるため、ネストの深さを d とすると、時間計算量は O(n + m·d) です。再帰呼び出しも d 回の深さに達します。100階層なら問題ありませんが、非常に深い入力ではコールスタックがあふれる可能性があります。たとえばPythonでは、デフォルトで1,000回のネストした呼び出しで停止します。
アルゴリズム
- すべての呼び出しで共有する位置
posを1つ用意し、最初の文字から始めます。 decode()は、posが文字列内にあり、]の位置にない間、ループします。- 英字の場合は、それを追加して先に進みます。
- 数字の場合は、数値全体
kを読み取り、[を読み飛ばし、本体に対してdecode()を呼び出し、]を読み飛ばして、本体をk回追加します。 - 構築したものを返します。最初の呼び出しは、デコードされた文字列を返します。
def decodeString(s):
pos = 0
def decode():
# Read from pos up to the ']' that closes this level, or the end.
nonlocal pos
parts = []
while pos < len(s) and s[pos] != "]":
if s[pos].isdigit():
times = 0
while s[pos].isdigit():
times = times * 10 + int(s[pos])
pos += 1
pos += 1 # skip '['
inner = decode() # the group's body, fully decoded
pos += 1 # skip ']'
parts.append(inner * times)
else:
parts.append(s[pos])
pos += 1
return "".join(parts)
return decode()スタックを使った1回の走査
考え方
再帰では、開いている各グループごとに未完成のテキストを1つ、呼び出しフレーム内に保持します。代わりに、それらのテキストを自分で用意したスタックに積み、1つのループで文字列を読み取ることができます。
現在のレベルについて、2つの値を追跡します。これまでにデコードしたテキストである current と、読み取り中の数値である count です。数字が現れたら、count × 10 + digit として count を更新するので、10 や 300 も正しく処理できます。[ が現れたらレベルを開き、current と count を積んでから、両方を初期化します。文字が現れたら current に追加します。] が現れたらレベルを閉じ、保存したテキストと数値を取り出します。そして current は、保存したテキストの後に current を count 回繰り返したものになります。
2[x3[yz]] をたどってみましょう。最初の [ で (空, 2) を積みます。x によって current は x になります。2つ目の [ で (x, 3) を積み、新しい current に yz が追加されます。最初の ] で (x, 3) を取り出すため、current は xyzyzyz になります。最後の ] で (空, 2) を取り出し、current は xyzyzyzxyzyzyz になります。
グループは開いた順序と逆の順序で閉じるため、スタックの先頭は常に ] で戻るレベルです。計算量は再帰の場合と同じ O(n + m·d) ですが、深くネストしても増えるのはリストだけで、呼び出しスタックは増えません。
アルゴリズム
- 空のスタック、空の
current、count = 0から始めます。 - 数字が来たら、
count = count × 10 + digitを設定します。 [が来たら、ペア（current、count）をプッシュし、その後currentを空に、countを0にリセットします。- 文字が来たら、それを
currentに追加します。 ]が来たら、（before、k）をポップし、currentをbeforeの後にcurrentをk回繰り返したものに設定します。- 最後の文字の後、
currentを返します。
def decodeString(s):
stack = [] # one entry per open '[': (the text before it, its count)
current = [] # pieces of the text at the current level
count = 0
for ch in s:
if ch.isdigit():
count = count * 10 + int(ch) # counts can have several digits
elif ch == "[":
stack.append((current, count))
current, count = [], 0
elif ch == "]":
before, times = stack.pop()
before.append("".join(current) * times)
current = before
else:
current.append(ch)
return "".join(current)
落とし穴と境界ケース
誤答の多くは、回数の読み取り方や、保存したテキストをどこに追加するかが原因です。
- 1桁だけを全体の回数として読む。
q10[w]eでは回数は10です。[の前の1桁だけを取り出すコードでは、wが0回繰り返されます。 - 回数をスタックに入れた後、
countを0に戻し忘れる。すると、次のグループの数字が古い数に加算されるため、2[a3[b]]では内側の回数が23として読み取られます。 - 保存したテキストより先に、繰り返した文字列を追加する。
]に到達したとき、結果はグループの前にあるテキストの後に繰り返した文字列を続けたものなので、ab2[c]はccabではなくabccです。 - 最上位の階層にある文字を失う。
2[ab]3[c]xのxはどの角括弧の外側にあっても、答えに含める必要があります。 - 変更できない長い文字列に、1文字ずつ追加する。追加のたびに文字列全体がコピーされることがあり、50,000文字の答えを何十億回ものコピーに変えてしまいます。リストまたは文字列ビルダーに断片を集めましょう。
よくある質問4
Decode String の時間計算量は何ですか？
入力の読み取りは O(n) です。出力の構築では、各文字をその文字が含まれるグループごとに1回コピーするため、合計で O(n + m·d) となります。m は復号後の長さ、d はネストの深さです。すべてのカウントが少なくとも 2 であれば、各グループはその周囲のグループの長さの半分以下なので、コピー量は 2m 未満に収まります。答え自体が m 文字あるため、どのような方法でも O(m) を下回ることはできません。
Decode String は再帰とスタックのどちらで解くべきでしょうか？
どちらも同じ処理を行います。再帰は、グループの本体がそれ自体でエンコードされた文字列になっているため、形式にそのまま従い、面接では最も速く書けることがよくあります。スタック版は1つのループで同じ処理を行い、未完了の外側の階層をリストに保持するため、非常に深いネストでも呼び出しスタックがオーバーフローしません。面接官から数千階層の深さにネストされた入力について聞かれたら、スタックを使う方法が答えです。
2桁以上のカウントはどのように扱いますか？
数を読み取りながら組み立てます。0から始め、各桁についてcount = count × 10 + digitを設定します。[が来たら数は完成なので、300[a]は300になります。数をスタックに積んだらすぐにcountを0にリセットしてください。そうしないと、次のグループの桁がその数に加算されてしまいます。
スタックはなぜ、各括弧の前にあったテキストを保存するのでしょうか？
[が開くと、そのレベルでここまでにデコードされたテキストはまだ完成していません。その後にグループのコピーを追加する必要があります。これをスタックに積んでおけば、空文字列から本体をデコードしている間も安全に保てます。一致する]が来たら、スタックから取り出すことでそのテキストが戻り、コピーを追加できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def decodeString(s):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "2[ab]3[c]x"
期待値
"ababcccx"