สมมติว่าเรามีสตริงสองตัว s และ t เราต้องหาว่าสตริง s สามารถต่อกันได้กี่ครั้งเพื่อสร้าง t หากไม่สามารถสร้าง t จาก s ได้ ให้คืนค่า -1
เช่น ถ้าอินพุตเป็น s = "tom", t = "tomtomtom" ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถต่อ "tom" 3 ครั้งเพื่อได้ "tomtomtom"
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
- ถ้าขนาดของ t ไม่หารขนาดของ s ลงตัว แล้ว
- คืนค่า -1
- cnt := ผลหารของ (ขนาดของ t / ขนาดของ s)
- s := ต่อ s จำนวน cnt ครั้ง
- ถ้า s เท่ากับ t แล้ว
- คืนค่า cnt
- คืนค่า -1
ลองดูการนำไปใช้ดังต่อไปนี้เพื่อเข้าใจได้ดียิ่งขึ้น:
ตัวอย่าง
def solve(s, t):
if(len(t) % len(s) != 0):
return -1
cnt = int(len(t) / len(s))
s = s * cnt
if(s == t):
return cnt
return -1
s = "tom"
t = "tomtomtom"
print(solve(s, t))
อินพุต
"tom", "tomtomtom"
ผลลัพธ์
3
