สมมติว่าเรามีสตริง s และ t สองสตริงที่มีขนาดเท่ากัน เราต้องตรวจสอบว่า s กับ t เท่ากันหรือไม่ มีเงื่อนไขบางประการที่ต้องตรวจสอบ:
- ทั้งสองมีค่าเท่ากัน หรือ
- หากเราแบ่ง s ออกเป็นสองสตริงย่อยที่อยู่ติดกันที่มีขนาดเท่ากัน และสตริงย่อยคือ s1 และ s2 และยังแบ่ง t เหมือนกัน เช่น s ออกเป็น t1 และ t2 ดังนั้นสิ่งใดสิ่งหนึ่งต่อไปนี้ควรถูกต้อง:
- s1 เรียกซ้ำเทียบเท่ากับ t1 และ s2 เรียกซ้ำเทียบเท่ากับ t2
- s1 เรียกซ้ำเทียบเท่ากับ t2 และ s2 เรียกซ้ำเทียบเท่ากับ t1
ดังนั้น หากอินพุตเป็น s ="ppqp" t ="pqpp" ผลลัพธ์จะเป็น True ราวกับว่าเราแบ่ง s และ t ออกเป็นสองส่วน s1 ="pp", s2 ="qp" และ t1 ="pq ", t2 ="pp" ในที่นี้ s1 =t2 และถ้าเราแบ่ง s2 และ t1 ออกเป็นสองส่วน s21 ="q", s22 ="p", t11 ="p", t12 ="q" ตรงนี้ s21 =t12 และ s22 =t11 ดังนั้นจึงเทียบเท่าแบบเรียกซ้ำ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน util() นี่จะใช้เวลา s
- ถ้าขนาด s เป็นเลขคี่
- คืนสินค้า
- left :=util(left half part of s)
- ขวา :=util(ครึ่งขวาของ s)
- คืนค่าต่ำสุดของ (ซ้ายต่อขวา), (ขวาต่อซ้าย)
- จากวิธีหลักคืนค่าจริงเมื่อ util(s) เหมือนกับ util(t) มิฉะนั้นเป็นเท็จ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
โค้ดตัวอย่าง
def util(s): if len(s) & 1 != 0: return s left = util(s[0:int(len(s) / 2)]) right = util(s[int(len(s) / 2):len(s)]) return min(left + right, right + left) def solve(s,t): return util(s) == util(t) s = "ppqp" t = "pqpp" print(solve(s, t))
อินพุต
"ppqp", "pqpp"
ผลลัพธ์
True
