ทฤษฎีโบราณนักบินอวกาศ: ตรวจสอบลำดับคำใน Python

ภาพรวม

โจทย์ตรวจสอบว่าสตริง s เรียงตามลำดับพจนานุกรมโบราณ (ancient dictionary order) หรือไม่ โดยพจนานุกรมกำหนดลำดับตัวอักษรที่อนุญาตและลำดับของมัน

ตัวอย่าง

dictionary = "bdc" (ลำดับ: b < d < c)

s = "bbbb h ddd i cccc"

ตัวอักษรใน dictionary ที่ปรากฏใน s: b, b, b, b, d, d, d, c, c, c, c → เรียงตาม b→d→c ✓ → True

อัลกอริทึม

1. i = 0 (pointer ใน dictionary)
2. วนลูปตัวอักษร c ใน s:
   • ถ้า c ไม่อยู่ใน dictionary → ข้าม
   • ถ้า c อยู่ใน dictionary:
     • ขยับ i จน dictionary[i] == c
     • ถ้า i เกินขอบ หรือ dictionary[i] != c → คืน False (ลำดับผิด)
3. จบลูป → คืน True

โค้ด Python

class Solution:
    def solve(self, astro_dict, s):
        l = len(astro_dict)
        if l == 0:
            return True
        i = 0
        for c in s:
            if c in astro_dict:
                while i < l and astro_dict[i] != c:
                    i += 1
                if i >= l or astro_dict[i] != c:
                    return False
        return True

ob = Solution()
print(ob.solve("bdc", "bbbb h ddd i cccc"))

ผลลัพธ์

True