Chương trình tìm số cách tạo chuỗi mục tiêu từ từ điển trong Python

Mô tả bài toán

Cho danh sách words (cùng độ dài) và chuỗi target. Tạo target từ trái sang phải: ký tự thứ i của target lấy từ ký tự thứ k của từ thứ j trong words. Sau khi dùng ký tự k của từ nào đó, không thể dùng ký tự x <= k của bất kỳ từ nào. Đếm số cách tạo target modulo 10^9+7.

Ví dụ

words = ["pqqp","qppq"], target = "qpq" -> 4 cách.

Giải thuật (DP + Memoization)

1. Tiền xử lý: d[j][c] = số từ có ký tự c tại vị trí j.
2. Đệ quy dfs(i, j): số cách tạo target[i:] bắt đầu từ cột j.
3. dfs(i, j) = dfs(i, j+1) + dfs(i+1, j+1) * d[j][target[i]] (bỏ cột j hoặc dùng cột j).
4. Cơ sở: i == len(target) -> 1; j == len(words[0]) -> 0.

Triển khai Python

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))

Đầu vào

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

Đầu ra

4