โปรแกรมค้นหาจำนวนลำดับย่อยที่แตกต่างกันใน Python

สมมติว่าเรามีสตริง s เราต้องนับจำนวนลำดับย่อยที่แตกต่างกันของสตริง s หากคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนผลลัพธ์ modulo 10^9 + 7

ดังนั้น หากอินพุตเป็น s ="bab" ผลลัพธ์จะเป็น 6 เพราะมี 6 ลำดับที่แตกต่างกัน ได้แก่ "a", "b, "ba", "ab", "bb", "abb" .

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

• dp :=อาร์เรย์ที่มีขนาดเท่ากับ s และเติม 0

• ม :=10^9 + 7

• สำหรับแต่ละดัชนี i และรายการอักขระใน s ทำ

  • ind :=ดัชนีของ i-th char ใน s จากขวา

  • dp[i] :=1 + (ผลรวมขององค์ประกอบทั้งหมดใน dp[จากดัชนี 0 ถึง i-1]) mod m หาก ind เหมือนกับ -1 มิฉะนั้น (ผลรวมขององค์ประกอบทั้งหมดใน 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