โปรแกรมนับจำนวนวิธีที่เราสามารถสร้างรายการค่าโดยแยกสตริงตัวเลขในPython

สมมติว่าเรามีสตริง s s มีตัวเลขตั้งแต่ 0 - 9 และเรายังมีตัวเลข k อีกตัว เราต้องหาจำนวนวิธีต่างๆ ที่สามารถแสดงเป็นรายการตัวเลขจาก [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]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=10^9 + 7

• N :=ขนาดของ s

• dp :=รายการขนาด (N + 1) และเติมด้วย 0

• dp[N] :=1

• สำหรับฉันในช่วง N − 1 ถึง 0, ลดลง 1 ทำ

  • curr_val :=0

  • สำหรับ j ในช่วง i ถึง N ทำ

    • curr_val :=curr_val * 10 + (s[j] เป็นตัวเลข)

    • ถ้า curr_val อยู่ในช่วง 1 ถึง k แล้ว

      • dp[i] :=(dp[i] + dp[j + 1]) mod ม

    • มิฉะนั้น

      • ออกจากวง

• กลับ 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