สมมติว่าเรามีสองสตริง s และ t เราต้องหาจำนวนการดำเนินการขั้นต่ำที่จำเป็นสำหรับ s เพื่อสร้าง t เป็นสตริงย่อยของ s ในการดำเนินการแต่ละครั้ง เราสามารถเลือกตำแหน่งใดก็ได้ใน s และเปลี่ยนอักขระในตำแหน่งนั้นเป็นอักขระอื่น
ดังนั้น หากอินพุตเป็น s ="abbpqr", t ="bbxy" ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถนำสตริงย่อย "bbpq" และเปลี่ยน 'p' เป็น 'x' และ 'q' เป็น ' ครับ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- k :=ขนาดของ t, n :=ขนาดของ s
- ตอบ :=10^10
- สำหรับฉันในช่วง 0 ถึง n - k ทำ
- ss :=สตริงย่อยของ s[จากดัชนี i ถึง i+k-1]
- ans :=ขั้นต่ำของ ans และจำนวนอักขระที่ไม่ตรงกันของ s และ t
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution:
def solve(self, s, t):
k, n = len(t), len(s)
ans = 10**10
for i in range(n - k + 1):
ss = s[i:i+k]
ans = min(ans, sum(ss[j]!=t[j] for j in range(k)))
return ans
ob = Solution()
print(ob.solve("abbpqr", "bbxy")) อินพุต
"abbpqr", "bbxy"
ผลลัพธ์
2
