Pythonで文字列を降順の連続する値に分割できるかどうかを確認するプログラム

数字だけの文字列sがあるとします。 sを2つ以上の空でない部分文字列に分割して、それらの部分文字列の数値が増加しない順序になり、隣接する2つの部分文字列ごとの数値の差が1になるかどうかを確認する必要があります。文字列はs="0080079"で、数値[80、79]を使用して["0080"、"079"]に分割できます。また、値は降順であり、隣接する値は1だけ異なるため、この方法は有効です。上記のようにsを分割できるかどうかを確認する必要があります。

したがって、入力がs ="080076"の場合、["08"、 "007"、 "6"]のように分割できるため、出力はTrueになり、数値は[8,7,6]になります。 。

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これには、s、pre、idx、nが必要です

• preが-1でなく、（sの部分文字列[インデックスidxからend]）の整数形式がpre -1と同じである場合、

  • Trueを返す

• 1からn-idx-1の範囲のiの場合、実行

  • curs：=s[インデックスidxからidx+i-1へ]の部分文字列

  • 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を返す

• 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