สมมติว่า เรามีสตริง 'i' ที่ประกอบด้วยตัวพิมพ์เล็กและจำนวนเต็ม 'j' อีกตัว เราต้องค้นหาว่ามีกี่สตริงที่มีขนาดเท่ากับ 'i' และมีขนาดเล็กกว่าหรือเท่ากับ 'i' พจนานุกรมศัพท์ และไม่มีอักขระที่เท่ากันติดต่อกันมากกว่า 'j'
คำตอบต้องคำนวณโดยการหา Mod ผลลัพธ์ 10 ^ 9 + 7.
ดังนั้น หากอินพุตเป็นเหมือน i ="app", j =2 เอาต์พุตจะเป็น 405
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ถ้า j <=0 แล้ว
-
คืนค่า 0
-
-
ม :=10 ^ 9 + 7
-
n :=ขนาดของ i
-
nums :=รายการใหม่ที่มี (การแสดง Unicode ของอักขระ - การแสดง Unicode ของ "a") สำหรับอักขระแต่ละตัวที่มีอยู่ใน s
-
คืนค่า dp(0, True, -1, 0) mod m
-
กำหนดฟังก์ชัน dp() นี่จะใช้เวลา pos ถูกผูกไว้ สุดท้าย นับ
-
ถ้า count> j ไม่ใช่ศูนย์ แล้ว
-
คืนค่า 0
-
-
ถ้า pos เหมือนกับ n แล้ว
-
กลับ 1
-
-
num :=nums[pos]
-
res :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง (num + 1 ถ้าถูกผูกไว้ มิฉะนั้น 26) ทำ
-
res :=res + dp(pos + 1, true if bound และ i เหมือนกับ num, i, count *(true if i is same as last) + 1)
-
-
ผลตอบแทน
-
-
จากวิธีหลักส่งคืน dp(0, True, -1, 0) % m
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution:
def solve(self, s, k):
if k <= 0:
return 0
MOD = 10 ** 9 + 7
n = len(s)
nums = [ord(char) - ord("a") for char in s]
def dp(pos, bound, last, count):
if count > k:
return 0
if pos == n:
return 1
num = nums[pos]
res = 0
for i in range(num + 1 if bound else 26):
res += dp(pos + 1, bound and i == num, i, count * (i == last) + 1)
return res
return dp(0, True, -1, 0) % MOD
ob = Solution()
print(ob.solve('app',2)) อินพุต
i = "app" j = 2
ผลลัพธ์
405
