Python程式：查詢不同子序列的數量

假設我們有一個字串 s，我們需要計算字串 s 的不同子序列的數量。如果答案過大，則返回結果模 10^9 + 7。

因此，如果輸入類似於 s = "bab"，則輸出將為 6，因為有 6 個不同的序列，它們是 "a"、"b"、"ba"、"ab"、"bb"、"abb"。

為了解決這個問題，我們將遵循以下步驟：

  • dp := 一個大小與 s 相同並填充 0 的陣列

  • m := 10^9 + 7

  • 對於每個索引 i 和專案 char 在 s 中，執行以下操作：

    • ind := s 中從右到左第 i 個字元的索引

    • 如果 ind 等於 -1，則 dp[i] := 1 + (dp[從索引 0 到 i-1] 中所有元素的總和) mod m，否則 (dp[從索引 ind 到 i-1] 中所有元素的總和) mod m

  • 返回 dp 中所有元素的總和 mod m

示例

讓我們檢視以下實現以更好地理解

def solve(s):
   dp, m = [0] * len(s), 10**9 + 7
   for i, char in enumerate(s):
      ind = s.rfind(char, 0, i)
      dp[i] = 1 + sum(dp[:i]) % m if ind == -1 else sum(dp[ind:i]) % m
   return sum(dp) % m

s = "bab"
print(solve(s))

輸入

"abcd", "abcdbcd"

輸出

6

更新於: 2021年10月7日

714 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告