ตรวจสอบว่าสามารถสร้างสตริง B จาก A ภายใต้ข้อจำกัดที่กำหนดใน Python . ได้หรือไม่

สมมติว่าเรามีสองสตริง s และ t และสองค่า p และ q เราต้องตรวจสอบว่าเป็นไปได้ไหมที่จะได้ t จาก s นั้น s ถูกแยกออกเป็นกลุ่ม p จำนวนอักขระ ยกเว้นกลุ่มสุดท้ายซึ่งจะมีอักขระ ≤ p และเราสามารถเลือกจำนวนอักขระสูงสุด q ได้จากแต่ละกลุ่ม และ ลำดับของอักขระใน t จะต้องเหมือนกับ s ด้วย

ดังนั้น หากอินพุตเป็น s ="mnonnopeqrst", t ="moprst", p =5, q =2 ผลลัพธ์จะเป็น True เนื่องจากเราสามารถแยกส่วนได้ เช่น "mnonn", "opeqr", "st" ตอนนี้โดยใช้สตริงย่อยอักขระ 2 ตัว "mo" และ "pr" จาก "mnonn" และ "opeqr" จากนั้น "st" ก็อยู่ที่นั่นแล้ว ดังนั้นการใช้สตริงย่อยความยาวทั้งสองนี้ เราจึงสามารถสร้าง t ได้โดยการต่อข้อมูลแบบง่ายๆ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• temp :=แผนที่ว่างที่มีรายการว่างสำหรับคีย์ทั้งหมด
• l :=รายการขนาดเท่ากับความยาวของ s และเติม 0
• สำหรับฉันในช่วง 0 ถึงขนาดของ s ทำ
  • แทรก i ที่ส่วนท้ายของ temp['a']
• ต่ำ :=0
• สำหรับ i ในช่วง 0 ถึงขนาด t - 1 ทำ
  • ดัชนี :=temp['a']
  • มัน :=ดัชนีที่จะแทรกต่ำในรายการดัชนีเพื่อรักษาลำดับการเรียงลำดับ
  • ถ้ามันเท่ากับขนาดของดัชนี - 1 แล้ว
    • คืนค่าเท็จ
  • จำนวน :=ผลหารของ (ดัชนี[it] / p)
  • l[นับ] :=l[นับ] + 1
  • ถ้า l[นับ]>=q แล้ว
    • นับ :=นับ + 1
    • ต่ำ :=นับ * p
  • มิฉะนั้น
    • ต่ำ :=ดัชนี[it] + 1
• คืนค่า True

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

from bisect import bisect_left
from collections import defaultdict
def solve(s, t, b, m) :
   temp = defaultdict(list)
   l = [0] * len(s)
   for i in range(len(s)) :
      temp['a'].append(i)
   low = 0
   for i in range(len(t)) :
      indices = temp['a']
      it = bisect_left(indices, low)
      if it == len(indices) :
         return False
      count = indices[it] // b
      l[count] = l[count] + 1
      if l[count] >= m :
         count += 1
         low = count * b
      else :
         low = indices[it] + 1
   return True
s = "mnonnopeqrst"
t = "moprst"
p = 5
q = 2
print (solve(s, t, p, q))

อินพุต

"mnonnopeqrst", "moprst", 5, 2

ผลลัพธ์

True