区間分割・連長圧縮

区間分割・連長圧縮

$ N $ 個の要素を区分に分割する問題は、比較的よく出題されます。

区分に分割する処理の一例として、連長圧縮 があります。

連長圧縮 は、"AAABBBBBAACDD" といった文字列を ('A', 3), ('B', 5), ('A', 2), ('C', 1), ('D', 2) のようにデータ１つ分と連続した長さとの組で表現します。

ソースコード

連長圧縮 を行うサンプルソースは次のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#--------- 入力例 ----------
s = 'AAABBBBBAACDD'
#---------------------------
n = len(s)      # 文字列の長さ
i = 0
while i < n:
    # s[j] != s[i] となる位置を探す
    j = i
    while j < n and s[j] == s[i]:
        j +=  1
    # 文字 s[i] が j - 1 文字連続したことがわかる
    print(s[i], j - i)
    # i を j の位置へ移動
    i = j

[実行結果]

A 3
B 5
A 2
C 1
D 2

文字列を区間ごとに分割することができました。