Pythonで数値文字列を分割して値のリストを作成できる方法の数をカウントするプログラム

文字列sがあるとします。 sには0〜9の数字が含まれており、別の数字kもあります。 sを[1、k]からの数のリストとして表すことができるさまざまな方法の数を見つける必要があります。答えが非常に大きい場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がs ="3456" k =500の場合、出力は7になります。これは、sを[3、4、5、6]、[34、5、6]、[3、 4、56]、[3、45、6]、[34、56]、[345、6]、[3、456]

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

• m：=10 ^ 9 + 7

• N：=sのサイズ

• dp：=サイズのリスト（N + 1）および0で埋める

• dp [N]：=1

• N − 1から0の範囲のiの場合、1ずつ減少します。

  • curr_val：=0

  • iからNの範囲のjについては、次のようにします

    • curr_val：=curr_val * 10 +（s [j] as number）

    • curr_valが1からkの範囲にある場合、

      • dp [i]：=（dp [i] + dp [j + 1]）mod m

    • それ以外の場合

      • ループから出てきます

• dp [0]

  を返します

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, s, k):
      m = 10 ** 9 + 7
      N = len(s)
      dp = [0] * (N + 1)
      dp[N] = 1
      for i in range(N − 1, −1, −1):
         curr_val = 0
         for j in range(i, N):
            curr_val = curr_val * 10 + int(s[j])
            if 1 <= curr_val <= k:
               dp[i] = (dp[i] + dp[j + 1]) % m
            else:
               break
      return dp[0]
ob = Solution()
s = "3456"
k = 500
print(ob.solve(s, k))

入力

"3456", 500

出力

7