Chương trình đếm chuỗi con khác nhau 1 ký tự trong Python

Cho 2 chuỗi s, t. Đếm số cách chọn chuỗi con không rỗng của s, thay đổi đúng 1 ký tự, thành chuỗi con của t.

Ví dụ: s="sts", t="tsts" → 6.

Giải thuật (Duyệt tất cả cặp vị trí bắt đầu)

1. Với mỗi cặp (i1, i2) vị trí bắt đầu trong s, t:
   • Mở rộng i,j cho bằng nhau.
   • Khi gặp ký tự khác: bỏ qua 1 ký tự (giả lập thay đổi), tăng ans, tiếp tục mở rộng phần còn lại, mỗi bước tăng ans.

Ví dụ minh họa

def solve(s, t):
    n1, n2 = len(s), len(t)
    ans = 0
    for i1, c1 in enumerate(s):
        for i2, c2 in enumerate(t):
            i, j = i1, i2
            while i < n1 and j < n2 and s[i] == t[j]:
                i += 1
                j += 1
            if i < n1 and j < n2 and s[i] != t[j]:
                i += 1
                j += 1
                ans += 1
                while i < n1 and j < n2 and s[i] == t[j]:
                    i += 1
                    j += 1
                    ans += 1
    return ans

s = "sts"
t = "tsts"
print(solve(s, t))

Đầu vào

"sts", "tsts"

Đầu ra

6