String Compression
英字からなる文字列 s が与えられます。これを圧縮します。連続する2文字以上の同じ文字の並びは、その文字の後に並びの長さを付けた形に置き換え、単独の文字はそのままにします。たとえば、aabccc は a2bc3 になります。圧縮した文字列を返してください。
大文字と小文字は異なる文字です。aA は長さ1の並びが2つです。
関数
- sstring
- 圧縮する文字列。英字のみ。
- 戻り値string
- 圧縮された文字列。各連続部分は、長さが1を超える場合、文字とその長さで表されます
制約
1 ≤ s.length ≤ 2 × 104sには英字のみが含まれます。aからzまで、およびAからZまでです。- ランレングスは10進数で表記され、複数の桁になることがあります。
例
- 入力
- s = "aabccc"
- 出力
- "a2bc3"
- 説明
- 連続する文字列は
aa、b、cccです。これらはa2、b（1文字だけの場合は個数が付きません）、c3になります。
- 入力
- s = "abbbbbbbbbbbb"
- 出力
- "ab12"
- 説明
aが1つ、続いてbが12個です。長さの12は1と2の2文字で表されるため、結果はab12です。
- 入力
- s = "zzZZZ"
- 出力
- "z2Z3"
- 説明
- 小文字の
zと大文字のZは異なる文字なので、これは2つ連続した後に3つ連続しています:z2Z3。
発展問題
逆の操作を書きます。ab12のような圧縮文字列が与えられたとき、元の文字列を復元します。複数の桁からなる回数は、どのように読み取ればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
sを、各ブロックが1つの文字を繰り返してできているブロックの列として読みます。ブロックを書き表すには、そのブロックについてどの2つの事実が必要ですか？各ブロックには、その文字と長さが必要です。ブロックの開始位置を示すインデックスを1つ保持し、同じ文字が続く間は2つ目のインデックスを進めます。2つのインデックスの間の距離が長さです。
iを連続部分の先頭に置き、s[j]が異なるか文字列の末尾に達するまでjを進めます。s[i]を書き出し、長さが1より大きい場合はj-iを10進数のテキストとして書き出し、iをjに移動します。12のような長さは2文字です。
解説
同じ文字が連続する各区間の開始位置と終了位置を見つけ、その長さをテキストとして書きます。1文字だけの区間には個数を書かず、個数は複数桁になることもあります。1つは区間の開始位置に、もう1つは区間の終わりまで走査する位置に置いた2つのインデックスで、1回の走査で処理できます。
実行結果を集めてから、書き込みます
考え方
まず、連続する文字列を文字と長さの組として記録します。たとえば、aabccc は (a, 2)、(b, 1)、(c, 3) となります。各文字は最後の連続部分を伸ばすか、新しい連続部分を開始します。次に、各連続部分の文字を書き、その長さが 1 より大きい場合は、その後に長さを書きます。
どちらの処理も O(n) です。隣り合う文字がどれも一致しない場合、リストには n 個の連続部分を格納できるため、追加の領域として O(n) が必要です。
アルゴリズム
- 空の連続文字リストを作成します。
sの各文字について、最後の連続文字が同じ文字なら、その長さに 1 を加えます。そうでなければ、長さ 1 の新しい連続文字を追加します。- 各連続文字について、その文字を書き、長さが 1 より大きい場合は、その長さを10進数のテキストとして書きます。
def compress(s):
# First pass: collect the runs as [letter, length] pairs
runs = []
for ch in s:
if runs and runs[-1][0] == ch:
runs[-1][1] += 1
else:
runs.append([ch, 1])
# Second pass: write each run, with its length when it is more than 1
parts = []
for letter, length in runs:
parts.append(letter)
if length > 1:
parts.append(str(length))
return "".join(parts)各連続区間を走査する2つのポインター
考え方
i は現在の連続部分の最初の文字に置き、s[j] が s[i] と等しい間、j を進めます。j が止まったとき、つまり異なる文字に達したとき、または末尾に達したとき、連続部分の長さは j-i です。その長さを書き出し、i = j とします。abbbbbbbbbbbb では、j はまず 1 で止まり、a が得られ、次に 13 で止まり、b12 が得られます。
内側のループが文字列の末尾で止まるため、最後の連続部分に特別な処理は必要ありません。j は前に進むだけなので、時間計算量は O(n) で、結果以外に保持するのは 2 つのインデックスだけです。R と Swift のバージョンは、まず s を文字配列に分割するため、追加の空間計算量は O(n) です。
アルゴリズム
i = 0に設定します。iが文字列の範囲内にある間、j = iに設定し、文字列の範囲内にあり、s[j]がs[i]と等しい間、jを前に進めます。s[i]を書き込みます。j-iが1より大きい場合は、10進数のテキストとして書き込みます。i = jに設定して、繰り返します。
def compress(s):
parts = []
n = len(s)
i = 0
while i < n:
# Move j to the first index after the run that starts at i
j = i
while j < n and s[j] == s[i]:
j += 1
parts.append(s[i])
if j - i > 1:
parts.append(str(j - i))
i = j
return "".join(parts)
落とし穴と境界ケース
- 異なる文字に出会ったときだけ、ひとまとまりを書き出すこと。
aabcccの最後のcccの後には何も続かないため、a2bを返します。 '0' + countのように、個数を1文字で書き出すこと。10で問題が起きます。bが12個なら、12の2文字が必要です。- 1文字だけの場合に
1を付けること。bはb1ではなく、bのままです。 - 大文字と小文字を区別しないこと。
zzZZZはz5ではなく、z2Z3です。 - JavaやC#のように、不変文字列を
+で拡張すること。各+はそれまでの結果をコピーするため、ループの計算量はO(n²)になります。文字列ビルダーを使いましょう。
よくある質問3
文字列圧縮の時間計算量はどのくらいですか？
2つのポインターを使った走査は、走査インデックスが前方にしか進まないため、O(n) 時間がかかります。結果とは別に2つのインデックスを保持するため、追加の領域は O(1) です。
圧縮後の文字列が元の文字列より長くなることはありますか？
このバージョンではそうなりません。単独の文字は1文字のままで、k ≥ 2 個の文字の連続は1文字とkの数字になり、k文字を超えることはありません。a1b1のように各文字の後に個数を書く方式では、長さが2倍になることがあります。
文字列をその場で圧縮するにはどうすればよいですか？
読み取りインデックスと書き込みインデックスを使って文字配列を処理します。読み取りインデックスで各連続部分を走査し、その文字と長さの桁を書き込みインデックスに書き込みます。出力は読み取り済みの入力より長くなることはないため、書き込みインデックスが読み取りインデックスを追い越すことはありません。最後に新しい長さを返します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def compress(s):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "aabccc"
期待される出力
"a2bc3"