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

สมมติว่าเรามีสตริงตัวพิมพ์เล็กสองสตริง s และ t เราต้องตรวจสอบว่า t สามารถสร้างขึ้นจาก s โดยใช้ข้อจำกัดต่อไปนี้หรือไม่ -

• อักขระของ t มีอยู่ใน s เช่น หากมี 'a' สองตัวใน t ดังนั้น s ก็ควรมี 'a' สองตัวด้วย

• เมื่ออักขระใดๆ ใน t ไม่อยู่ใน s ให้ตรวจสอบว่าอักขระสองตัวก่อนหน้า (ค่า ASCII สองค่าก่อนหน้า) มีอยู่ใน s หรือไม่ ตัวอย่างเช่น หาก 'f' อยู่ใน t แต่ไม่อยู่ใน s ดังนั้น 'd' และ 'e' สามารถใช้จาก s เพื่อสร้าง 'f' ได้

ดังนั้น หากอินพุตเป็นเหมือน s ="pghn" t ="pin" ผลลัพธ์จะเป็น True เนื่องจากเราสามารถสร้าง 'i' จาก 'g' และ 'h' เพื่อสร้าง "pin" ได้

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

• ความถี่ :=ความถี่ของอักขระแต่ละตัวในหน่วย s
• สำหรับ i ในช่วง 0 ถึงขนาดของ t ทำ
  • ถ้า freq[t[i]] ไม่ใช่ศูนย์ ดังนั้น
    • ความถี่[t[i]] :=ความถี่[t[i]] - 1
  • มิฉะนั้น เมื่อ freq[อักขระก่อนหน้าตัวแรกของ t[i]] และ freq[อักขระตัวที่สองก่อนหน้าของ t[i]] ไม่เป็นศูนย์ ดังนั้น
    • ลด freq[อักขระก่อนหน้าตัวแรกของ t[i]] ลง 1
    • ลด freq[อักขระตัวที่สองก่อนหน้าของ t[i]] ลง 1
  • มิฉะนั้น
    • คืนค่าเท็จ
• คืนค่า True

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

ตัวอย่าง

from collections import defaultdict
def solve(s, t):
   freq = defaultdict(lambda:0)
   for i in range(0, len(s)):
      freq[s[i]] += 1
   for i in range(0, len(t)):
      if freq[t[i]]:
         freq[t[i]] -= 1
      elif (freq[chr(ord(t[i]) - 1)] and freq[chr(ord(t[i]) - 2)]):
         freq[chr(ord(t[i]) - 1)] -= 1
         freq[chr(ord(t[i]) - 2)] -= 1
      else:
         return False
   return True
s = "pghn"
t = "pin"
print(solve(s, t))

อินพุต

"pghn", "pin"

ผลลัพธ์

True