Pythonで文字列を降順に連続する数値へ分割できるか判定するプログラム

問題の概要

数字のみで構成された文字列 s が与えられたとします。この文字列を2つ以上の空でない部分文字列に分割でき、かつ各部分文字列の数値が降順（非増加順）で並んでいて、隣り合う部分文字列の数値の差がすべて 1 であるかどうかを判定するのが目的です。

例えば、文字列が s = "0080079" の場合、["0080", "079"] と分割すると、その数値は [80, 79] となります。値は降順に並んでおり、隣接する値の差も1なので、これは有効な分割です。

入力例

s = "080076" の場合、出力は True になります。なぜなら、["08", "007", "6"] と分割すると、数値は [8, 7, 6] となり、条件を満たすからです。

解決のアプローチ

この問題は深さ優先探索（DFS）を使って解くことができます。手順は以下の通りです。

• 関数 dfs() を定義します。引数として s（文字列）、pre（前の数値）、idx（現在のインデックス）、n（文字列の長さ）を受け取ります。
• pre が -1 ではなく、残りの部分文字列 s[idx:] を整数に変換した値が pre - 1 と等しい場合、True を返します。
• i を 1 から n - idx - 1 まで繰り返します。
  • curs := 部分文字列 s[idx : idx+i]
  • cur := curs を整数に変換した値
  • pre が -1 の場合（最初の分割）：dfs(s, cur, idx+i, n) が True なら True を返します。
  • それ以外の場合：cur == pre - 1 かつ dfs(s, cur, idx+i, n) が True なら True を返します。
• ループが終わっても見つからなければ False を返します。
• メイン処理では以下を行います。
  • n := 文字列 s の長さ
  • n <= 1 の場合は False を返します（2つ以上に分割できないため）。
  • それ以外は dfs(s, -1, 0, n) の結果を返します。

実装例

理解を深めるために、以下の実装を見てみましょう。

def dfs(s, pre, idx, n):
    if pre != -1 and int(s[idx:]) == pre - 1:
        return True
    for i in range(1, n-idx):
        curs = s[idx: idx+i]
        cur = int(curs)
        if pre == -1:
            if dfs(s, cur, idx+i, n):
                return True
        else:
            if cur == pre - 1 and dfs(s, cur, idx+i, n):
                return True
    return False

def solve(s):
    n = len(s)
    if n <= 1:
        return False
    return dfs(s, -1, 0, n)

s = "080076"
print(solve(s))

入力

"080076"

出力

True

まとめ

このアルゴリズムでは、DFSによって可能なすべての分割パターンを試行し、隣接する数値が必ず1ずつ減少する条件を満たす分割が存在するかどうかを再帰的に確認しています。先頭のゼロを含む部分文字列も int() で変換すれば正しく数値として扱えるため、「008」のような表記でも問題なく動作します。計算量は最悪情况下 O(2^n) となりますが、実際には枝刈りにより効率的に動作します。