ค้นหาลำดับย่อย "programmingquestion" ในสตริงด้วย Python

ภาพรวม

โจทย์นี้ตรวจสอบว่าสามารถหาคำว่า "programmingquestion" ได้จากสตริงที่กำหนด โดยเลือกตัวอักษรที่มีดัชนีห่างกันเท่ากัน (arithmetic progression) กล่าวคือ ต้องหาตัวอักษร 'p' และ 'r' แรก แล้วตรวจสอบว่าข้ามช่องว่างคงที่แล้วได้คำเต็มหรือไม่

ตัวอย่าง

อินพุต: "pzrzozgzrzazmzmziznzgzqzuzezsztzizozn"

เอาต์พุต: True

ขั้นตอนการแก้ปัญหา

1. เก็บดัชนีของตัวอักษร 'p' ทั้งหมดในรายการ p
2. เก็บดัชนีของตัวอักษร 'r' ทั้งหมดในรายการ r
3. วนลูปคู่ (j, k) โดยที่ j ∈ p, k ∈ r และ k > j
4. คำนวณช่วงข้าม step = k - j
5. ตรวจสอบว่าสลายนิพจน์ s[j:len(s):step] มีคำ "programmingquestion" หรือไม่
6. ถ้าพบ ให้คืน True, มิฉะนั้น False

โค้ด Python

class Solution:
    def solve(self, s):
        p = [i for i, c in enumerate(s) if c == "p"]
        r = [i for i, c in enumerate(s) if c == "r"]
        for j in p:
            for k in r:
                if k > j:
                    if "programmingquestion" in s[j:len(s):k-j]:
                        return True
        return False

ob = Solution()
s = "pzrzozgzrzazmzmziznzgzqzuzezsztzizozn"
print(ob.solve(s))

การทำงาน

• หา 'p' ที่ดัชนี 0, 'r' ที่ดัชนี 2 → step = 2
• สไลด์ s[0::2] ได้ "programmingquestion" → พบ!

ผลลัพธ์

True