【Python】再起処理で文字列を圧縮

現在Recursionに取り組んでいる。 そこで学んだことをメモする。

---

テキストデータの圧縮

Recursionの練習問題で、以下のような問題が出た。

# 文字列を以下のように圧縮する関数を書け

"aaabbbbccd" → "a3b4c2d"

この関数は再起処理を用いるとシンプルに実装できたのでメモ。

def compress(s):
    # ベースケース
    if s == "": return ""

    # 先頭の文字が、何文字連続しているかを数える
    count = countChar(s, s[0])

    if count == 1:
        return s[0] + compress(s[1:])
    else:
        return s[0] + str(count) + compress(s[count:])


# 先頭の文字列が何文字連続しているか取得
def countChar(s, targetChar):
    #　ベースケース
    if s == "" or s[0] != targetChar: return 0

    return countChar(s[1:], targetChar) + 1

上記のコードではcompress(s)がエントリーポイントになる。

渡された文字列が空文字の場合は、空文字を返却するベースケースを用意。 もし空文字以外ならば先頭の文字が何文字連続しているかをcountChar(s, targetChar)で カウントして返却値の先頭に先頭の文字+文字数(1ならば省略)を加えて再帰処理。

これで文字列の圧縮が可能。

再帰処理のコツについては前回のポストを参照。

note-tmk.hatenablog.com