ข้อ 11 · LC392 Is Subsequence 🟢

ให้ string (สตริง) s และ t จง return True ถ้า s เป็น subsequence ของ t

subsequence คือ string ที่ได้จากการลบตัวอักษรบางตัว (หรือไม่ลบเลย) ออกจาก t โดย ไม่สลับลำดับ ตัวที่เหลือ — ต่างจาก substring ที่ต้องติดกันเป็นพืด

ลองเองก่อน 10–15 นาที

def is_subsequence(s: str, t: str) -> bool:
    # เขียนโค้ดของคุณที่นี่
    pass


print(is_subsequence("abc", "ahbgdc"))   # ควรได้ True
print(is_subsequence("axc", "ahbgdc"))   # ควรได้ False
print(is_subsequence("", "abc"))         # ควรได้ True

i = 0                          # ตอนนี้กำลังหา s[i]
for c in t:                    # ไล่ทุกตัวอักษรของ t ทางเดียว
    if ______ and ______:      # (1) ยังหาไม่ครบ  และ  (2) ตัวอักษรตรงกัน
        i += 1                 # คว้าไว้ แล้วไปหาตัวถัดไปของ s
return ______                  # (3) เงื่อนไขว่าสำเร็จ

ไล่ทีละสเต็ปด้วยมือ (dry run)

ไล่ s = "abc", t = "ahbgdc" ดูว่า i ขยับตอนไหน

จบแล้ว i = 3 = len(s) → return True — และสังเกตว่า i หยุดที่ 3 พอดี ถ้า t ยาวต่อไปอีก เงื่อนไข i < len(s) จะกัน IndexError ให้เรา

ทำไมมันถูกต้อง: พิสูจน์ว่า "คว้าตัวซ้ายสุด" ไม่เคยพลาด

นี่คือส่วนที่สำคัญที่สุดของข้อนี้ และเป็นคำถามที่คนสงสัยจริง ๆ ตอนเห็นโค้ดสั้นแบบนี้: ถ้าเจอตัวอักษรที่ตรงกันแล้วคว้าเลยทันที ไม่เก็บไว้เผื่อว่าจะมีตัวหลังที่ "เหมาะกว่า" มันจะไม่พลาดคำตอบเหรอ

ก่อนอื่นต้องเข้าใจว่าความกลัวนี้มีเหตุผล เพราะในโจทย์แบบเลือกของหลายข้อ การคว้าของชิ้นแรกที่เจอมักทำให้เสียของชิ้นที่ดีกว่าไปจริง ๆ แต่ข้อนี้ไม่เป็นแบบนั้น และเหตุผลพิสูจน์ได้ตรง ๆ

วิธีพิสูจน์เรียกว่า exchange argument (การแลกเปลี่ยน) หลักการคือ: สมมติว่ามีคำตอบที่ถูกต้องอยู่ชุดหนึ่ง แล้วแสดงว่าเราสามารถ ดัดแปลง คำตอบชุดนั้นให้กลายเป็นคำตอบแบบที่โค้ดของเราหาได้ โดยที่มันยังถูกต้องอยู่ ถ้าทำได้ แปลว่าโค้ดของเราไม่เคยพลาด

สมมติมีวิธีจับคู่ที่ถูกต้องอยู่ ซึ่งเลือกตัวอักษร s[0] จากตำแหน่ง q ใน t
และโค้ดของเราจะคว้าตำแหน่ง p ซึ่งเป็นตำแหน่งซ้ายสุดที่ตรงกัน  ->  p <= q

t = . . . [p] . . . [q] . . . . . . . . . .
           ↑         ↑
      เราคว้าตัวนี้   คำตอบสมมติใช้ตัวนี้

ย้ายจาก q มาใช้ p แทน:
  - ตัวอักษรยังตรงกันเหมือนกัน (ทั้งสองตำแหน่งเป็นตัวอักษร s[0])
  - ตัวที่เหลือของ s เดิมหาได้ในช่วงขวาของ q
  - ช่วงขวาของ p ครอบช่วงขวาของ q ทั้งหมด (เพราะ p <= q)
  -> ตัวที่เหลือจึงยังหาได้ครบเหมือนเดิมแน่นอน

ประโยคที่สำคัญที่สุดคือบรรทัดที่สามจากล่าง: เมื่อเราเลือกตำแหน่งที่ซ้ายกว่า พื้นที่ค้นหาที่เหลือทางขวาจะ กว้างกว่าหรือเท่ากับ เดิมเสมอ ไม่มีทางแคบลง ดังนั้นการคว้าตัวซ้ายสุดจึงไม่เคยทำให้เราแย่ลง — อย่างมากก็เท่ากัน อย่างน้อยก็ดีกว่า

ทำซ้ำเหตุผลนี้กับตัวอักษรตัวที่สอง ตัวที่สาม ไปเรื่อย ๆ จะได้ว่าคำตอบสมมติทุกชุดสามารถถูกดัดแปลงมาเป็นคำตอบที่โค้ดเราหาได้ ดังนั้นถ้ามีคำตอบอยู่จริง โค้ดเราจะหามันเจอแน่นอน

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0                              # (1) ตัวชี้บน s = กำลังตามหา s[i]
        for c in t:                        # (2) ตัวชี้บน t กวาดทางเดียว ไม่ย้อน
            if i < len(s) and s[i] == c:   # (3) ยังหาไม่ครบ และตัวอักษรตรงกัน
                i += 1                     # (4) คว้าตัวนี้ แล้วไปหาตัวถัดไปของ s
        return i == len(s)                 # (5) ขยับครบทุกตัว = เจอครบตามลำดับ

from bisect import bisect_right
from collections import defaultdict


class Matcher:
    def __init__(self, t: str):
        self.pos = defaultdict(list)          # ตัวอักษร -> list ของ index ใน t
        for idx, ch in enumerate(t):
            self.pos[ch].append(idx)

    def is_subsequence(self, s: str) -> bool:
        cur = -1                              # ตำแหน่งล่าสุดที่ใช้ไปใน t
        for ch in s:
            idxs = self.pos.get(ch)
            if not idxs:
                return False                  # ไม่มีตัวอักษรนี้ใน t เลย
            k = bisect_right(idxs, cur)       # หา index แรกที่ > cur
            if k == len(idxs):
                return False                  # มีแต่ตัวที่อยู่ซ้ายกว่าที่ใช้ไปแล้ว
            cur = idxs[k]
        return True


m = Matcher("ahbgdc")
for q in ["abc", "axc", "", "acb", "ahbgdc", "abcd"]:
    print(repr(q), m.is_subsequence(q))

'abc' True
'axc' False
'' True
'acb' False
'ahbgdc' True
'abcd' False