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

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

• ตัวอักษรของ t ต้องมีใน s เช่น ถ้ามี 'a' สองตัวใน t แล้ว s ต้องมี 'a' สองตัวเช่นกัน

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

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

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:

• freq := ความถี่ของแต่ละตัวอักษรใน s
• สำหรับ i ในช่วง 0 ถึงขนาดของ t ทำ
  • ถ้า freq[t[i]] ไม่ใช่ศูนย์ แล้ว
    • freq[t[i]] := freq[t[i]] - 1
  • มิฉะนั้นถ้า freq[ตัวอักษรก่อนหน้า 1 ของ t[i]] และ freq[ตัวอักษรก่อนหน้า 2 ของ t[i]] ไม่ใช่ศูนย์ แล้ว
    • ลด freq[ตัวอักษรก่อนหน้า 1 ของ t[i]] ลง 1
    • ลด freq[ตัวอักษรก่อนหน้า 2 ของ t[i]] ลง 1
  • มิฉะนั้น
    • คืนค่า False
• คืนค่า 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