โปรแกรมนับสตริงย่อยที่ต่างกันแค่หนึ่งตัวอักษรใน Python

ปัญหา

สตริง s และ t หาจำนวนวิธีเลือกสตริงย่อยของ s แล้วเปลี่ยนตัวอักษร 1 ตัว ให้ได้สตริงย่อยของ t

ตัวอย่าง

s="sts", t="tsts" → ผลลัพธ์ 6

ขั้นตอนการแก้ปัญหา

1. n1 := len(s), n2 := len(t), ans := 0
2. วน i1, c1 ใน s, i2, c2 ใน t:
   • i := i1, j := i2
   • ขยายขณะ s[i] == t[j]: i+=1, j+=1
   • ถ้า i < n1 and j < n2 and s[i] != t[j]:
     • i+=1, j+=1, ans+=1
     • ขยายต่อขณะ s[i] == t[j]: i+=1, j+=1, ans+=1
3. คืน ans

การนำไปใช้งาน (Python)

def solve(s, t):
    n1 = len(s)
    n2 = len(t)
    ans = 0
    for i1, c1 in enumerate(s):
        for i2, c2 in enumerate(t):
            i = i1
            j = 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))

อินพุต

"sts", "tsts"

เอาต์พุต

6