สมมติว่าเรามีสองสตริง s และ t เราสามารถลบ t ออกจาก s กี่ครั้งก็ได้ และ t ปรากฏขึ้นทีละครั้งเท่านั้น เราต้องตรวจสอบว่า s สามารถว่างได้หรือไม่โดยลบ t ออกหลาย ๆ ครั้งตามที่ต้องการ
ดังนั้น หากอินพุตเป็น s ="pipipinnn" t ="pin" ผลลัพธ์จะเป็น True เนื่องจากเราสามารถลบ "pin" ออกจาก "pipipinnn" ได้ เราก็จะได้ "pipinn" ลบ "pin" ออกอีกครั้ง รับสตริง "พิน" แล้วเอาออกเพื่อให้ว่าง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ในขณะที่ขนาดของ s> 0, do
- ตำแหน่ง :=ดัชนีเริ่มต้นของ t ใน s
- ถ้าตำแหน่งไม่อยู่ใน s แล้ว
- ออกมาจากวงจร
- s :=ลบ t ออกจาก s หนึ่งครั้ง
- คืนค่า จริง เมื่อขนาดของ s เท่ากับ 0 มิฉะนั้น เท็จ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def solve(s, t): while len(s) > 0: position = s.find(t) if position == -1: break s = s.replace(t, "", 1) return len(s) == 0 s = "pipipinnn" t = "pin" print(solve(s, t))
อินพุต
"pipipinnn", "pin"
ผลลัพธ์
True
