โปรแกรมสร้างเป้าหมายโดยลบจากอันแรกหรืออันสุดท้ายแล้วแทรกอีกครั้งใน Python

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

ดังนั้น หากอินพุตเป็น s ="zyvxw" t ="vwxyz" ผลลัพธ์จะเป็น 3 เนื่องจากการดำเนินการเหล่านี้คือ:ลบ "w" และใส่ไว้หลัง "v" เพื่อรับ "zyvwx" Remove "z" และแทรกหลัง "x" เพื่อรับ "yvwxz" ลบ "y" และใส่หลัง "x" เพื่อรับ "vwxyz"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ans :=ขนาดของ s, n :=ขนาดของ s

• สำหรับผมอยู่ในช่วง 0 ถึง n-1 ทำ

  • k :=0

  • สำหรับ j ในช่วง i ถึง n-1 ทำ

    • สำหรับ k ในช่วง k ถึงขนาดของ t ทำ

      • ถ้า s[j] เหมือนกับ t[k] แล้ว

        • ans :=ขั้นต่ำของ ans และ n - (j - i + 1)

        • ออกจากวง

    • k :=k + 1

  • กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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