文字が連続して続く場合の文字列の圧縮

Question

実現したいこと

文字列の圧縮

前提

Hodge は文章を短く表示するアプリを作成しており、文字が連続して 2 回以上続く場合は文字を数字に置き換えようと考えています。アルファベットで書かれた文字列 s が与えられるので、再帰を使って連続で続いた文字を数字に置き換える、stringCompression という関数を作成してください。

stringCompression("aaabbb") --> a3b3
stringCompression("aaabbbc") --> a3b3c
stringCompression("aaabbbCCL") --> a3b3C2L
stringCompression("aaabbbCCLL") --> a3b3C2L2
stringCompression("abceeaaaddbbb") --> abce2a3d2b3
stringCompression("aaabbbaaaaccaaaaba") --> a3b3a4c2a4ba
stringCompression("a") --> a

ヒント

0番目のaがどれくらい連続しているか調べるために、0番目と1番目を比較、0番目とと2番目を比較… というように調べていきます。比較して2つの値が異なったときに、文字と連続した数値を戻り値に加えていきましょう。

発生している問題・エラーメッセージ

解き方が分からない（分からないなりに、なるべく頑張って途中まで書いたコードを記載します。）

試したいこと

解き方が皆目検討が付かず、上記ヒント以外で何か助言をいただけると幸いです。

該当のソースコード

def stringCompression(s):
    # 関数を完成させてください
    for i in range(len(s)):
        if stringCompression(s[i]) == stringCompression(s[i+1]):
            count += 1
        return stringCompression(s[i])+count

Comments

[melian]

itertools の groupby 関数を使うとよさそうです。

効率的なループ実行のためのイテレータ生成関数 — Python 3.11.3 ドキュメント
https://docs.python.org/ja/3/library/itertools.html#itertools.groupby

[1T2R3M4]

https://www.youtube.com/watch?v=1HBD0X7Kcgo

Answer 1

習っていると思いますが、再帰は以下のことを考えて作ります。

• 一段階進むにはどうすればいいか
  一番左のものを圧縮して、残りを圧縮する。
  例) aaabbbcc を圧縮したもの ー> a3 + bbbcc を圧縮したもの。
• どうなると終端で結果は？
  すべての文字が同じであれば、数えて圧縮して返す。
  例) ccを圧縮 ー> c2

まずはこれで考えてみてください。

作ると以下のようになります。 説明のためにだいぶ冗長に書きました。

def stringCompression(s):
    for i in range(len(s)):   # 1文字ずつ順に見ていく。
        if s[i] != s[0]:         #先頭と違う文字が出たら数えおわり
            if i == 1:
                len_str = ""     # 文字の個数は1個だったらなにも無し
            else:
                len_str = f"{i}" # その他は数文字の個数

            compressed = f"{s[0]}{len_str}" # 圧縮した表現

            remainder = s[i:]    # 残りの文字列

            return compressed + stringCompression(remainder)
        
    else:    # 全部同じ文字だったら
        compressed = f"{s[0]}{i+1}"  # 全部数えて圧縮
        return compressed

簡潔に書くとこんな感じ

def stringCompression(s):
    for i in range(len(s)):
        if s[i] != s[0]:
            return f"{s[0]}{i if i != 1 else ''}" + stringCompression(s[i:])
    else:
        return f"{s[0]}{i+1}"

Answer 2

上記ヒント以外で何か助言をいただけると幸いです。

ヒントの話以外をしろと言っているところにヒントの話をして申し訳ないのですが、
このヒントは例えばこういう意味です:

def stringCompression(s):
    for i in range(1,len(s)): # 0番目のaがどれくらい連続しているか調べるために、0番目と1番目を比較、0番目とと2番目を比較… というように調べていきます。
        if s[0] != s[i]: # 比較して2つの値が異なったときに
            return s[0] + (str(i) if i>1 else "") + stringCompression(s[i:]) # 文字と連続した数値を戻り値に加えていきましょう。

あとはifに入らずforを抜けたらどうすんだとか、
空文字が渡されたとか
そういう細かいケースを考えて付け加えて終わりです

Answer 3

まず「連続する文字」と「その個数」を保持する変数を用意します。
そして、文字列の先頭から順に、以下のような処理を行います。

• 連続する文字と同じなら個数だけを増やします。
• 異なる文字になれば、連続する文字と個数を更新します。

def f(s, pos=0, c='', cnt=0):
    if pos >= len(s):
        print(f'{c}が{cnt}個')
        return # 終わり

    cur = s[pos]
    if cur == c: # 同じなら個数が増えるだけ
        cnt += 1
    else:        # 異なれば連続する文字を更新する
        print(f'{c}が{cnt}個')
        c, cnt = cur, 1

    return f(s, pos+1, c, cnt)

f('aabcc')

上記のコードにおいてprintしているところを、結果の文字列として蓄積して返すように修正すると目的の処理ができます。
なお、提示コードのようにループを使うと「そもそも再帰イラナクネ？」となりそうですが。