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

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

เช่น ถ้าอินพุตคือ s = "95643" t = "45963" ผลลัพธ์จะเป็น True เพราะเราสามารถแปลงได้ดังนี้: "95643" → "95463" → "45963"

วิธีแก้ปัญหา

• places := แมปที่ค่าเริ่มต้นเป็นลิสต์
• สำหรับ i ในช่วงขนาดของ s ลงมา 0:
  • key := s[i] เป็นจำนวนเต็ม
  • เพิ่ม i ลงท้าย places[key]
• สำหรับแต่ละ e ใน t:
  • key := e เป็นจำนวนเต็ม
  • ถ้า places[key] ว่าง: return False
  • i := องค์ประกอบสุดท้ายของ places[key]
  • สำหรับ j ในช่วง 0 ถึง key - 1:
    • ถ้า places[j] ไม่ว่างและองค์ประกอบสุดท้ายของ places[j] < i: return False
  • ลบองค์ประกอบสุดท้ายออกจาก places[key]
• return 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