資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：找出相同長度的字串
假設我們有一個字串 'i'，它包含小寫字母，以及另一個整數 'j'。我們需要找出有多少個字串與 'i' 的長度相同，並且在字典序上小於或等於 'i'，並且沒有連續的相同字元超過 'j' 個。
答案需要透過對結果取模 10 ^ 9 + 7 來計算。
因此，如果輸入像 i = "app"，j = 2，那麼輸出將是 405。
為了解決這個問題，我們將遵循以下步驟：
如果 j <= 0，則
返回 0
m := 10 ^ 9 + 7
n := i 的長度
nums := 一個新列表，包含 s 中每個字元的（字元的 Unicode 表示 - "a" 的 Unicode 表示）
返回 dp(0, True, -1, 0) mod m
定義一個函式 dp()。它將接收 pos、bound、last、count 作為引數
如果 count > j 不為零，則
返回 0
如果 pos 等於 n，則
返回 1
num := nums[pos]
res := 0
對於 i 從 0 到 (num + 1 如果 bound，否則 26)，執行以下操作：
res := res + dp(pos + 1, true 如果 bound 並且 i 等於 num，i, count *(true 如果 i 等於 last) + 1)
返回 res
從主方法返回 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
更新於： 2020-12-23
112 次瀏覽
廣告