Pythonで解く「Count and Say（数えて言う）」問題のアルゴリズムと実装

この記事では、有名な文字列処理のアルゴリズム問題である「Count and Say（数えて言う）」数列について、その仕組みとPythonでの実装方法を詳しく解説します。

Count and Say 数列とは？

Count and Say 数列は、直前の項を「読み上げる」ことで次の項を生成していく特殊な数列です。最初のいくつかの項は以下のようになります。

• 1
• 11
• 21
• 1211
• 111221

数列の生成ルール

この数列は、前の項を「数字を数えながら声に出して読む」というルールに従って作られます。具体的には以下の通りです。

• 1（イチ）→ 最初の項は単に「1」
• 11（1が1つ）→ 前の項「1」を読んで「1が1個」と表現
• 21（2が1つ、つまり「1が2つ」）→ 前の項「11」を読んで「1が2個」と表現
• 1211（1が1つ、2が1つ）→ 前の項「21」を読んで「2が1個、1が1個」と表現
• 111221（1が1つ、1が1つ、2が2つ）→ 前の項「1211」を読んで「1が1個、2が1個、1が2個」と表現

問題の定義

整数 n（1 ≤ n ≤ 30）が与えられたとき、Count and Say 数列の第 n 項を文字列として返すことが求められます。

解法のアプローチ

この問題は、連続する同じ数字を「ランレングス圧縮（Run-Length Encoding）」のように数え上げることで解けます。手順は以下の通りです。

1. 初期値として s := "1" を設定します。
2. n = 1 の場合は、そのまま s を返します。
3. i が 2 から n までの範囲で以下を繰り返します。
   • j := 0、temp := ""、curr := ""、count := 0 として初期化します。
   • j が s の長さ未満である間、以下を繰り返します。
     • curr が空文字列なら、curr := s[j]、count := 1 とし、j を 1 増やします。
     • curr が s[j] と同じなら、count と j をそれぞれ 1 増やします。
     • それ以外の場合は、temp に count（文字列化）と curr を連結し、curr := ""、count := 0 にリセットします。
   • ループ終了後、temp に残った count と curr を連結し、s := temp とします。
4. 最終的な s を返します。

Pythonでの実装例

それでは、上記のアルゴリズムを実際のPythonコードで見てみましょう。

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        s = "1"
        if n == 1:
            return s
        for i in range(2, n + 1):
            j = 0
            temp = ""
            curr = ""
            count = 0
            while j < len(s):
                if curr == "":
                    curr = s[j]
                    count = 1
                    j += 1
                elif curr == s[j]:
                    count += 1
                    j += 1
                else:
                    temp += str(count) + curr
                    curr = ""
                    count = 0
            temp += str(count) + curr
            s = temp
        return s

ob1 = Solution()
print(ob1.countAndSay(6))

入力

print(ob1.countAndSay(6))

出力

312211

コードのポイント

この実装では、変数 curr で現在注目している文字を追跡し、count でその連続出現回数をカウントしています。異なる文字が出現したタイミングで、「回数 + 文字」の形式で結果文字列 temp に追加していくのが核心部分です。計算量は各項の長さに比例するため、n ≤ 30 の制約下でも十分高速に動作します。