โปรแกรมสร้างเป้าหมายโดยการนำตัวอักษรแรกหรือสุดท้ายออกและแทรกใหม่ใน Python

สมมติว่ามีสตริงสองตัว S และ T ที่เป็นการเรียงสับเปลี่ยนของกัน มีการดำเนินการที่นำตัวอักษรแรกหรือสุดท้ายของ S ออกและแทรกที่ตำแหน่งใดก็ได้ในสตริง หาจำนวนการดำเนินการขั้นต่ำเพื่อแปลง S ให้เป็น T

เช่น ถ้าอินพุตคือ s = "zyvxw" t = "vwxyz" ผลลัพธ์จะเป็น 3

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

• ans := ขนาดของ s, n := ขนาดของ s
• for i ในช่วง 0 ถึง n-1 ทำ
  • k := 0
  • for j ในช่วง i ถึง n-1 ทำ
    • for k ในช่วง k ถึงขนาดของ t ทำ
      • ถ้า s[j] เท่ากับ t[k] แล้ว ans := min(ans, n - (j - i + 1)) ออกจากลูป
    • k := k + 1
• คืนค่า ans

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

class Solution:
    def solve(self, s, t):
        ans = n = len(s)
        for i in range(n):
            k = 0
            for j in range(i, n):
                for k in range(k, len(t)):
                    if s[j] == t[k]:
                        ans = min(ans, n - (j - i + 1))
                        break
                k += 1
        return ans

ob = Solution()
s = "zyvxw"
t = "vwxyz"
print(ob.solve(s, t))

อินพุต

"zyvxw", "vwxyz"

เอาต์พุต

5