สมมติว่าเรามีสตริงที่ไม่ว่างสองสตริง s และ t ที่มีความยาวเท่ากัน เราต้องแบ่งมันออกเป็นสตริงย่อยเพื่อให้สตริงย่อย s และ t แต่ละคู่มีขนาดเท่ากันและเป็นแอนนาแกรมของกันและกัน ตอนนี้ให้หาดัชนีการตัดเพื่อให้ได้จำนวนการตัดสูงสุดของ s และ t หากไม่พบผลลัพธ์ ให้ส่งคืนรายการว่าง
ดังนั้น หากอินพุตเป็น s ="bowcattiger" t ="owbactietgr" ผลลัพธ์จะเป็น [0, 3, 5, 6, 10] เนื่องจากเราสามารถแบ่งสตริงออกเป็น 5 พาร์ติชั่น โดยแต่ละสตริงจะเป็น แอนนาแกรมของกันและกัน s =["โค้ง", "ca", "t", "tige", "r"], t =["owb", "ac", "t", "ietg", "r"]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ช่วงเวลา :=รายการใหม่
- cs :=แผนที่ที่มีอักขระเป็น s และความถี่
- ct :=แผนที่ที่มีอักขระเป็น t และความถี่
- ถ้า cs ไม่เหมือนกับ ct แล้ว
- คืนรายการใหม่
- สำหรับ x ในขนาดช่วงของ s - 1 เหลือ 0 ทำ
- cs[s[x]] :=cs[s[x]] - 1
- ct[t[x]] :=ct[t[x]] - 1
- ถ้า cs เหมือนกับ ct แล้ว
- แทรก x ที่ส่วนท้ายของช่วงเวลา
- เรียงลำดับช่วงเวลาของรายการแล้วกลับ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
from collections import Counter class Solution: def solve(self, a, b): intervals = [] ca = Counter(a) cb = Counter(b) if ca != cb: return [] for x in reversed(range(len(a))): ca[a[x]] -= 1 cb[b[x]] -= 1 if ca == cb: intervals.append(x) return sorted(intervals) ob = Solution() s = "bowcattiger" t = "owbactietgr" print(ob.solve(s, t))
อินพุต
"bowcattiger", "owbactietgr"
ผลลัพธ์
[0, 3, 5, 6, 10]
