โปรแกรมหาจำนวนวิธีสร้างสตริงเป้าหมายจากพจนานุกรมใน Python

มีลิสต์ words ความยาวเท่ากัน และสตริง target สร้าง target จากซ้ายไปขวา: ตัวอักษรที่ i ของ target ใช้ตัวอักษรที่ k ของ word[j] ได้ถ้าเท่ากัน และหลังใช้ k แล้ว ห้ามใช้ตำแหน่ง ≤ k ของ word ใดๆ อีก หาจำนวนวิธี (มอด 10^9+7)

ตัวอย่าง: words=["pqqp","qppq"], target="qpq" ผลลัพธ์ 4

วิธีแก้ปัญหา (DP + Memoization)

1. d[j][c] = จำนวน word ที่มีตัวอักษร c ที่ตำแหน่ง j
2. dfs(i, j) = วิธีสร้าง target[i:] เริ่มจากคอลัมน์ j:
   • dfs(i, j+1) (ข้ามคอลัมน์ j)
   • dfs(i+1, j+1) * d[j][target[i]] (ใช้คอลัมน์ j)

ตัวอย่างโค้ด

from collections import Counter

def solve(words, target):
    m, n = len(words[0]), len(target)
    d = [Counter() for _ in range(m)]
    for w in words:
        for j, c in enumerate(w):
            d[j][c] += 1
    def dfs(i, j):
        if i == n: return 1
        if j == m: return 0
        return (dfs(i, j+1) + dfs(i+1, j+1) * d[j][target[i]]) % int(1e9+7)
    return dfs(0, 0)

words = ["pqqp","qppq"]
target = "qpq"
print(solve(words, target))

อินพุต

["pqqp","qppq"], "qpq"

เอาต์พุต

4