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回現れます。
発展問題
デコードされた文字列は、入力よりはるかに長くなることがあります。長さが10^18に達する可能性がある場合、文字列を構築せずに位置iの文字を返すにはどうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
角括弧の中身がわかるまでは
3[...]を書き出すことはできません。また、中にはさらに多くのグループが含まれていることがあります。どの種類のグループなら、いつでもすぐに解読できますか？中にグループを含まないグループは一度に展開できるため、内側から外側へ処理します。
]が現れたら、それが閉じるグループは完成です。その[の前で待機していたテキストと回数が必要になります。これまでに作ったテキストと、読み取った数を保持しながら、一度走査します。
[に遭遇したら、両方をスタックに積み、新しく始めます。]に遭遇したら、それらを取り出し、現在のテキストを繰り返したものを、取り出したテキストに追加します。10や300も扱えるように、カウントは桁ごとに組み立てます。
解説
グループの本体がわかるまでは、そのグループのコピーを書き出せません。また、本体の中にさらにグループが含まれることもあります。そのため、どの方法でも最も内側のグループから処理します。文字列を内側から書き換える方法、各本体を再帰的に処理する方法、または未処理の外側のグループをスタックに保持する方法です。ここで、n は入力の長さ、m はデコード後の長さ、d はネストの深さです。
最も内側のグループを展開し、その後繰り返します
考え方
中にグループを含まないグループを見つけ、その複製をその場に書き出して、もう一度確認します。最初の ] は必ずそのようなグループを閉じます。それより前に閉じられたグループはないため、その本体には括弧がありません。その左側で最も近い [ が対応する括弧で、その前に続く数字が繰り返し回数です。2[x3[yz]] では、まず 3[yz] が展開され、2[xyzyzyz] になります。さらにもう一度展開すると、答えが得られます。
展開のたびに文字列全体を作り直します。グループが b 個あり、出力が m 文字の場合、コピー回数は最大で b × m になります。デコード後に 50,000 文字になるグループが 1,000 個ある場合、コピー回数は最大で 5 × 10^7 です。
アルゴリズム
- 最初の
]を探します。見つからない場合は、文字列を返します。 - 左に向かって最も近い
[を探します。その間のテキストが本体です。 - その
[の前にある数字を、回数kとして読み取ります。 - 最初の数字から
]までのすべてを、本体をk回繰り返したものに置き換え、これを繰り返します。
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:]再帰下降
考え方
エンコードされた文字列は文字とグループの並びであり、グループの本体もまたエンコードされた文字列です。そこで、1つの関数 decode が共有位置から読み取り、] に到達するか入力の末尾に達するまで処理します。その際、各グループの本体に対して自分自身を呼び出します。その呼び出しは対応する ] で停止します。それより深い ] はすべて、より深い呼び出しで消費されているからです。2[x3[yz]] の場合、最も内側の呼び出しは yz を返し、真ん中の呼び出しは xyzyzyz を返し、外側の呼び出しはそれを2回書き出します。
入力の各文字は1回ずつ読み取られますが、出力文字はそれを囲むグループごとに1回コピーされます。時間計算量は O(n + m·d) です。再帰の深さは d 回の呼び出しになります。
アルゴリズム
- すべての呼び出しで共有される位置
posを1つ保持し、0から開始します。 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[x3[yz]]では、まず(empty, 2)、次に(x, 3)を積みます。最初の]で(x, 3)を取り出し、currentはxyzyzyzになります。最後の]で(empty, 2)を取り出し、それを2倍にします。処理量は再帰の場合と同じO(n + m·d)ですが、深い入れ子によって増えるのはリストであり、呼び出しスタックではありません。
アルゴリズム
- 空のスタック、空の
current、およびcount = 0から始めます。 - 数字の場合、
count = count × 10 + digitを設定します。 [の場合、(current,count)をプッシュし、その後両方をリセットします。- 文字の場合、それを
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です。[の前の数字だけを取ると、wは0回繰り返されます。 countをプッシュした後に0へリセットしない。すると、次のグループの数字が古い数に続いてしまうため、2[a3[b]]では内側の個数が23として読み取られます。- 保存したテキストより前に複製を置く。
ab2[c]はccabではなくabccです。 - 最上位の文字を落とす。
2[ab]3[c]xのxは答えに含まれます。 - 変更不可能な文字列に1文字ずつ追加する。追加のたびに文字列全体がコピーされる可能性があるため、50,000文字の答えでは10億回を超える文字コピーが発生します。ピースをリストまたは文字列ビルダーに集めましょう。
よくある質問3
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になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def decodeString(s):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "2[ab]3[c]x"
期待される出力
"ababcccx"