【Python】文字列に連続して降順に並ぶ整数が含まれているか判定するプログラム

はじめに

数字だけで構成された文字列 s が与えられ、「その文字列の中に、連続して降順に並ぶ整数が含まれているかどうか」を判定することを考えます。

たとえば、入力が s = "99989796" の場合、この文字列は [99, 98, 97, 96] という連続した降順の整数列として分割できるため、出力は True になります。

アルゴリズムの考え方

この問題は、先頭から何桁分を最初の整数として切り出すかを順に試しながら、残りの部分が「前の値 − 1」という規則で続いているかを再帰的に確認するバックトラッキングで解くことができます。具体的な手順は次のとおりです。

1. 引数に pos(現在の位置)と prev_num(直前の整数)を受け取る補助関数 helper() を定義します。
2. pos が文字列の長さ n と一致したら、末尾まで処理できたということなので True を返します。
3. prev_num の桁数を num_digits とします。
4. i を num_digits − 1 から num_digits の範囲でループさせます。
   これは、10 → 9 や 100 → 99 のように桁数が減る連続にも対応するためです。各 i について、s[pos : pos+i] の数値が prev_num − 1 と一致するなら、helper(pos + i, prev_num − 1) を再帰的に呼び出し、その結果が True であれば True を返します。
5. どの長さでも一致しなければ False を返します。

メイン処理の流れ

• n := 文字列 s の長さ
• i を 1 から n ÷ 2 までループします(最初の整数は最大でも文字列の半分の長さまで)
  ・num := 先頭 i 桁 s[0:i] を数値化したもの
  ・helper(i, num) が True を返せば、全体として True
• すべて試しても成立しなければ False を返します。

実装例(Python)

class Solution:
   def solve(self, s):
      n = len(s)

      def helper(pos, prev_num):
         if pos == n:
            return True
         num_digits = len(str(prev_num))
         for i in range(num_digits - 1, num_digits + 1):
            if s[pos:pos+i] and int(s[pos:pos+i]) == prev_num - 1:
               if helper(pos + i, prev_num - 1):
                  return True
         return False

      for i in range(1, n // 2 + 1):
         num = int(s[:i])
         if helper(i, num):
            return True
      return False

ob = Solution()
s = "99989796"
print(ob.solve(s))

入力

"99989796"

出力

True

コードのポイント

• 桁数の変化への対応: ループ範囲を num_digits − 1 から始めることで、100 → 99 のように桁数が1つ減る連続にも柔軟に対応できます。
• 先頭の切り出し幅: 最初の整数が文字列全体の半分より長くなることはないため、n//2 まで試せば十分です。
• 再帰による判定の伝播: helper() が文字列の終端(pos == n)に到達できれば、すべての要素が「前の値 − 1」でつながっていたことになります。

まとめ

本記事では、与えられた数字列が「連続して降順に並ぶ整数」を含むかどうかを判定するPythonプログラムを紹介しました。再帰的なバックトラッキングを用いることで、桁数が変わるケースも含めて正確に判定できる点が大きな特徴です。同様の手法は、昇順の連続判定や分割可能な数列の検証など、さまざまな文字列処理の問題に応用できます。