โปรแกรมตรวจสอบสตริงว่าสามารถแปลงได้ด้วยการดำเนินการเรียงลำดับสตริงย่อยใน Python

สมมติว่าเรามีสตริงตัวเลขสองสตริง s และ t เราต้องการเปลี่ยนจากสตริง s เป็น t โดยใช้การดำเนินการต่อไปนี้กี่ครั้งก็ได้:1. เลือกสตริงย่อยที่ไม่ว่างใน s และจัดเรียงแบบแทนที่เพื่อให้อักขระอยู่ในลำดับจากน้อยไปมาก เราต้องตรวจสอบก่อนว่าสามารถเปลี่ยน string s เป็น string t ได้หรือไม่

ดังนั้น หากอินพุตเป็นแบบ s ="95643" t ="45963" ผลลัพธ์จะเป็น True เพราะเราสามารถแปลง s เป็น t ได้โดยใช้ เช่น "95643" -> "95463" -> "45963"

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

• สถานที่ :=แผนที่ที่ประเภทค่าเริ่มต้นคือรายการ

• สำหรับฉันในช่วงขนาด s ลงไปที่ 0 ทำ

  • คีย์ :=s[i] เป็นจำนวนเต็ม

  • ใส่ i ต่อท้ายสถานที่[คีย์]

• สำหรับแต่ละ e ใน t ทำ

  • คีย์ :=e เป็นจำนวนเต็ม

    • ถ้า places[key] ว่างเปล่า แสดงว่า

      • คืนค่าเท็จ

    • i :=องค์ประกอบสุดท้ายของสถานที่[คีย์]

    • สำหรับ j ในช่วง 0 ถึงคีย์ - 1 ทำ

      • ถ้า places[j] ไม่ว่างเปล่าและเป็นองค์ประกอบสุดท้ายของ places[j]

        • คืนค่าเท็จ

    • ลบองค์ประกอบสุดท้ายออกจากสถานที่[คีย์]

• คืนค่า True

from collections import defaultdict
def solve(s, t):
   places = defaultdict(list)
   for i in reversed(range(len(s))):
      key = int(s[i])
      places[key].append(i)

   for e in t:
      key = int(e)
      if not places[key]:
         return False
      i = places[key][-1]
      for j in range(key):
         if places[j] and places[j][-1] < i:
            return False
      places[key].pop()
   return True

s = "95643"
t = "45963"
print(solve(s, t))

"95643", "45963"

True