สมมติว่าเรามีสตริงสองตัว s และ t เราสามารถลบ t ออกจาก s ได้ไม่จำกัดครั้ง และ t ปรากฏเพียงครั้งเดียวในแต่ละครั้ง เราต้องตรวจสอบว่า s สามารถว่างเปล่าได้โดยการลบ t ตามจำนวนครั้งที่ต้องการหรือไม่
เช่น ถ้าอินพุตเป็น s = "pipipinnn", t = "pin" ผลลัพธ์จะเป็น True เนื่องจากเราลบ "pin" จาก "pipipinnn" ได้ "pipinn" ลบอีกครั้งได้ "pin" ลบอีกครั้งได้สตริงว่าง
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
- while ขนาดของ s > 0 ทำ
- position := ดัชนีเริ่มต้นของ t ใน s
- ถ้า position ไม่อยู่ใน s แล้ว
- ออกจากลูป
- s := ลบ t ออกจาก s หนึ่งครั้ง
- คืนค่า true เมื่อขนาดของ s เท่ากับ 0 มิฉะนั้น false
ลองดูการนำไปใช้ดังต่อไปนี้เพื่อเข้าใจได้ดียิ่งขึ้น:
ตัวอย่าง
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
